首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。