首页 > 代码库 > NOJ 1072 The longest same color grid（尺取）
NOJ 1072 The longest same color grid（尺取）
Problem 1072: The longest same color grid
Time Limits: 1000 MS Memory Limits: 65536 KB
64-bit interger IO format: %lld Java class name: Main
Description
There are n grid, m kind of color. Grid number 1 to N, color number 1 to M.
The color of each grid is painted in one of the m colors. Now let you remove the Grid does not exceed K, get a new sequence.
Ask you the same color and continuous length of the grid sequence is the length of the number?
Input
The first line of input T, T group data. (T <= 20)
The next line of input three numbers n, m and k. (1 < n, m，k <= 10^5)
The next line of input n number, indicating that the color of each grid. (1 <= a[i] <= m)
Output
For each group of data output the same color and continuous grid sequence length.
Sample Input
110 2 21 2 1 2 1 1 2 1 1 2
Output for Sample Input
5
Hint
For example we can delete the fourth position and the seventh position
题意：给你一个连续的数字染色序列，你最多可以去掉k个格子使得某些格子变成连续的，比如样例的去掉第二和第四个格子，中间的便有5个1是连续的……
学长出的题，刚看到真的是跪了，1e5的范围知道肯定不能两个for去暴力，想过尺取法，然而只是在原序列上进行尺取，这样并不知道到底删除[L，R]中哪几个点才能得到最大的连续长度。
后来学长说是用vector数组记录每一种颜色所出现的下标，对每一种颜色的vector进行尺取，若设左右游标为L、R，则区间内的元素下标就是 $vector[color][Li……Ri]$，区间总长度（闭区间）为 $vector[color][R]-vector[color][L]+1$，所删除的块为记为 $cnt$个，则可获得 $vector[color][R]-vector[color][L]+1-cnt$，依次对每一个颜色的vector进行尺取更新答案即可
代码：
#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define CLR(arr,val) memset(arr,val,sizeof(arr))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=1e5+7;int arr[N];vector<int>vec[N];void init(int m){ for (int i=0; i<=m; ++i)//这里写成 <m 又让我WA了一次，苦逼 vec[i].clear();}int main(void){ int tcase,n,m,k,i,color; scanf("%d",&tcase); while (tcase--) { scanf("%d%d%d",&n,&m,&k); init(m); for (i=1; i<=n; ++i) { scanf("%d",&color); vec[color].push_back(i-1); //printf("%d<-%d\n",color,i-1); } int ans=1; for (i=1; i<=m; ++i) { if(vec[i].empty()) continue; int L=0,R=0; int cnt=0; int SZ=vec[i].size(); while (L<SZ) { while (R<SZ) { ++R; if(R>=SZ) { --R; break; } //printf("[%d %d]\n",vec[i][R-1],vec[i][R]); cnt=cnt+vec[i][R]-vec[i][R-1]-1; if(cnt>k) { cnt=cnt-(vec[i][R]-vec[i][R-1]-1); --R; break; } } int now=vec[i][R]-vec[i][L]-cnt+1; if(now>ans) ans=now; ++L; if(L>=SZ) break; else cnt=cnt-(vec[i][L]-vec[i][L-1]-1); } } printf("%d\n",ans); } return 0;}NOJ 1072 The longest same color grid（尺取）