设为首页 加入收藏

TOP

HDU 1027 Ignatius and the Princess II 选择序列题解
2015-07-20 17:52:36 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 1027 Ignatius and the Princess 选择 序列 题解

直接选择序列的方法解本题，但是最坏时间效率是O(n*n)，故此不能达到0MS。

使用删除优化，那么就可以达到0MS了。

删除优化就是当需要删除数组中的元素为第一个元素的时候，那么就直接移动数组的头指针就可以了，那么时间效率就是O(1)了，而普通的删除那么时间效率是O(n)，故此大大优化了程序。

如何直接选择第k个序列，可以参考本博客的Leetcode题解。Leetcode题有个一模一样的题目。不过没有使用删除优化。

?

看见本题的讨论中基本上都是使用STL解，还有沾沾自喜的家伙，不过使用STL解决本题虽然是可以，但是那是因为本题的数据很弱；

因为使用STL的时间效率是O(n*m)，其中n可能是1000， 而m可能是10000，故此会达到1千万的数据处理，随便增加个大数据用例就会超时。

故此使用STL来解决本题其实是很次，很初级的解法了。

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             using namespace std; const int MAX_N = 1001; int arr[MAX_N], N, M, tbl[MAX_N]; void genSeqNum() { int mth = M-1; memset(tbl, 0, sizeof(int) * N); tbl[N-1] = 0; for (int i = N-2, d = 2; i >= 0 && mth > 0; i--, d++) { tbl[i] = mth % d; mth /= d; } } void eraseNth(int A[], int i) { --N; for (; i < N; i++) { A[i] = A[i+1]; } } void printNums() { genSeqNum(); int *A = arr; printf("%d", A[tbl[0]]); if (!tbl[0]) A++, N--; else eraseNth(A, tbl[0]); int t = 1;//定位tbl下标 while (N > 0)//优化之后的算法 { for (; N && !tbl[t]; t++)//主要优化地方 { printf(" %d", *A);//输出为零的，不用使用删除函数 A++, N--;//重新定位数列 } if (!N) break;//已经输出完毕 printf(" %d", A[tbl[t]]);//不为零的选择，使用删除函数 eraseNth(A, tbl[t]); t++; } putchar('\n'); } int main() { while (scanf("%d %d", &N, &M) != EOF) { for (int i = 0; i < N; i++) { arr[i] = i+1; } printNums(); } return 0; }


?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：POJ 1149 PIGS(最大流+建图) 下一篇：poj1273--Drainage Ditches（最大..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: