codeforces B. Xenia and Ringroad 解题报告

题目链接：http://codeforces.com/problemset/problem/339/B

题目理解不难，这句是解题的关键 In order to complete the i-th task, she needs to be in the house number a_i and complete all tasks with numbers less than i 。从样例1的提示，可以知道，如果a[i] > a[i+1]，则需要继续顺时针走下去，直到到达n，接着重新从1开始数，直到a[i+1]。

这里要注意的是题目中 2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵，暗示了我们数据是比较大的，为什么呢？如果输入的序列是递减的，那么每一次转换到下一个数都要经过一次循环，最坏情况是10^5 * 10^5，即10^10 = 10 000 000 000，所以需要要用到64位整数[-2^63, 2^63)，即即-9223372036854775808~9223372036854775807。常规的32位整数只能够处理40亿以下的数。

 #include <iostream>

 #include <stdio.h>

 #include <stdlib.h>

 using namespace std;

 const int maxn =  + ;

 typedef long long LL;    // 关键

 int main()

 {

     int i, j, m, n;

     LL a[maxn];

     LL cnt, cnt1;    // cnt用来统计时间的总和，cnt1用来统计已经完成的任务

     while (cin >> n >> m)

     {

         for (i = ; i < m; i++)

         {

             scanf("%I64d", &a[i]);

         }

         for (cnt = -, cnt1 = i = , j = ; i < m; i++)

         {

             while (a[i] >= j)

             {

                 j++;

                 cnt++;

             }

             cnt1++;

             if (a[i+] < a[i] && i+ < m)

             {

                 j--;   // 退出while过程中，j加多了一次，需要减回来再统计

                 while (j != n)

                 {

                     j++;    // 必须要达到n之后才能继续从1开始数到a[i+1]

                     cnt++;

                 }

                 j = ;   // j到达n之后要继续开始新一轮的顺时针计数(从1开始)

             }

             if (cnt1 == m)   // 所有任务已经完成则退出

                 break;

         }

         printf("%I64d\n", cnt);

     }

     return ;

 }

优化后的代码（以时间换空间的，上面那个是30ms，800kB，GNU C++提交，下面的是156ms，0kB，MS C++提交）

 #include <iostream>

 #include <stdio.h>

 #include <stdlib.h>

 using namespace std;

 int main()

 {

     _int64 cnt;

     int t1, t2, i, k,  m, n;

     while (cin >> n >> m)

     {

         t2 = ;

         k = ;

         for (cnt = i = ; i < m; i++)

         {

             cin >> t1;

             if (t1 < t2)

                 k = n;

             cnt += k + t1 - t2;

             k = ;

             t2 = t1;

         }

         printf("%I64d\n", cnt);

     }

     return ;

 }

巴特西

codeforces B. Xenia and Ringroad 解题报告

最新文章

热门文章