九度oj 题目1496：数列区间

题目描述：: 有一段长度为n(1<=n<=1000000)的数列，数列中的数字从左至右从1到n编号。初始时数列中的数字都是0。
接下来我们会对其进行m（1<=m<=100000）次操作，每次操作都会将区间[l,r]内的所有数字都变为一个特定的数字，并且每次操作这个特定的数字都不相同。
我们可以简单的认为，第一次操作时将给定区间内的数字都变为1，第二次将给定区间内数字都变为2，第三次变为3，以此类推。
在经过m次操作完成后，要求输出该数列中，拥有相同正整数（不包括0）的最长连续区间长度。
若n = 5，m = 3，原数列00000
第一次操作区间[1,3],
数列变为11100
第二次操作区间[3,4],
数列变为11220
第三次操作区间[3,5]
数列变为11333
则最长连续区间为[3,5]拥有共同正整数3，故输出其长度3。

输入：: 输入包含多组测试数据，每组测试数据第一行为两个整数n，m。
接下去m行，每行两个整数l，r，表示该次操作区间为[l,r]。（1<=l<=r<=n）

输出：: 对于每组测试数据输出为一个整数，表示拥有相同正整数（不包括0）的最长连续区间长度。

样例输入：

样例输出：

3

5

如果从前往后操作，费事费力。
因为保存的总是最后的结果，所以我们可以从后向前操作。
前面的操作只可以修改数列中为0的位。

为节省时间，用一个next数组记录每一位右侧第一位为0的位置
代码如下

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <queue>

 using namespace std;

 typedef pair<int, int> Opr;

 Opr op[];

 int num[];

 int nextm[];

 int main() {

     int n, m;

     while (scanf("%d %d", &n, &m) != EOF) {

         memset(num, , sizeof(num));

         for (int i = ; i <= n; i++) {

             nextm[i] = i + ;

         }

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

             scanf("%d %d", &op[i].first, &op[i].second);

         }

         for (int i = m; i > ; i--) {

             int from = op[i].first, to = op[i].second;

             for (int j = from; j <= to;) {

                 if (num[j] == ) {

                     num[j] = i;

                 }

                 int tmp = nextm[j];

                 nextm[j] = nextm[to];

                 j = tmp;

             }

         }

         /*for (int i = 1; i <= n; i++) {

             printf("%d ", num[i]);

         }

         puts("");*/

         int ans = ;

         int tmp = ;

         for (int i = ; i <= n+; i++) {

             if (num[i] == num[i - ] && num[i] != ) {

                 tmp++;

             }

             else {

                 if (ans < tmp) {

                     ans = tmp;

                 }

                 tmp = ;

             }

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

九度oj 题目1496：数列区间

最新文章

热门文章