首页 > 代码库 > 2014 Super Training #8 B Consecutive Blocks --排序+贪心

2014 Super Training #8 B Consecutive Blocks --排序+贪心

当时不知道怎么下手,后来一看原来就是排个序然后乱搞就行了。

解法不想写了,可见:http://blog.csdn.net/u013368721/article/details/28071241

其实就是滑动窗口的思想。

代码:

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>using namespace std;#define N 100007#define M 33struct node{    int col,ind;}p[N];int cmp(node ka,node kb){    if(ka.col == kb.col)        return ka.ind < kb.ind;    return ka.col < kb.col;}int main(){    int i,j,now,cnt,L;    int n,m;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1;i<=n;i++)        {            scanf("%d",&p[i].col);            p[i].ind = i;        }        sort(p+1,p+n+1,cmp);        L = 1;        now = m;        cnt = 1;        int maxi = 1;        for(i=2;i<=n;i++)        {            if(p[i].col == p[i-1].col)            {                now -= (p[i].ind-p[i-1].ind-1);                cnt++;                while(now < 0)  //滑动                {                    now += p[L+1].ind-p[L].ind-1;                    cnt--;                    L++;                }                maxi = max(maxi,cnt);            }            else            {                maxi = max(cnt,maxi);                now = m;                L = i;                cnt = 1;            }        }        maxi = max(maxi,cnt);        printf("%d\n",maxi);    }    return 0;}
View Code