【jzoj4911】【人生的叹息】【贪心】

题目大意

把一个长度为n的序列a[i]分成x份每一份的花费不能超过k，每一分的花费为，求最少分成多少份。

解题思路

可以考虑贪心，因为能把一个数放进当前块就尽量放这样肯定更优，算花费的时候用桶计算就可以了。

code

#include<cmath> #include<cstdio> #include<algorithm> #define LL long long #define min(a,b) ((a<b)?a:b) #define max(a,b) ((a>b)?a:b) #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const maxn=5*1e5; int n,a[maxn+10],cnt[maxn+10];LL K; int read(){ int v=0;char ch=getchar(); for(;(ch<'0')||(ch>'9');ch=getchar()); for(;(ch>='0')&&(ch<='9');v=v*10+ch-'0',ch=getchar()); return v; } int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d%lld",&n,&K); fo(i,1,n)a[i]=read(); int i=1,ans=0;LL tmp=0; fo(j,1,n){ if(tmp+cnt[a[j]]>K){ tmp=0;ans++; fo(k,i,j-1)cnt[a[k]]--; i=j; } tmp+=cnt[a[j]]; cnt[a[j]]++; } printf("%d",ans+1); return 0; }