rqnoj-231- 我爱面包 -dp

本文主要是介绍rqnoj-231- 我爱面包 -dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

就是从后往前搜，一个前指针st，一个后指针ed；

如果后指针ed往后走的过程中出现了可以吃的面包序列。

那么就把st指针尽量的往后走。

这过程中出现的最优值即是答案。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define INF 9999999
#define maxn 1000011
int a[maxn];
int num[maxn];
int sum[maxn];
int vis[maxn];
struct list
{int x;int y;
} node[maxn];
int cmp1(struct list a,struct list b)
{return a.x<b.x;
}
int cmp2(struct list a,struct list b)
{return a.y<b.y;
}
int main()
{int n,k,i;int su,p;scanf("%d%d",&n,&k);su=0;for(i=0; i<n; i++){scanf("%d",&node[i].x);node[i].y=i;}sort(node,node+n,cmp1);su=1;int tt;tt=node[0].x;node[0].x=su;for(i=1; i<n; i++){if(node[i].x!=tt){tt=node[i].x;su++;node[i].x=su;}else{node[i].x=su;}}sort(node,node+n,cmp2);for(i=0; i<n; i++){a[i]=node[i].x;}int st,ed;st=0;int ss,ee;ss=0,ee=-1;for(i=0; i<n; i++){num[a[i]]++;if(num[a[i]]==k)su--;if(su==0){ed=i;if(ee==-1)ee=ed;for(st; st<=i; st++){p=num[a[st]];if(p>k){num[a[st]]--;}else{break;}}if(ed-st<ee-ss){ss=st;ee=ed;}}}if(ee==-1){cout<<"-1"<<endl;}else{cout<<ss+1<<" "<<ee+1<<endl;}return 0;
}

这篇关于rqnoj-231- 我爱面包 -dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---