NOJ 1072 The longest same color grid（尺取）

2022-10-07 11:25:43

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

1

10 2 2

1 2 1 2 1 1 2 1 1 2

Output for Sample Input

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;

}

码农公寓