description
一开始有n个非负整数hi,接下来会进行m次操作,第i次操作给出一个数c[i],要求你选出c[i]个大于零的数并将它们减去1。
问最多可以进行多少轮操作后无法操作(即没有c[i]个大于零的数)
analysis
明显每次都减去最大的那几个,减不了了就\(GG\)
那么先把\(a\)排序了,考虑怎么一次次减掉\(a\)最前面的几个
但是直接减最前面的次序会乱掉,比如\(5,5,5,4,4,4,3,2,1\)减去最大的四个
那么考虑二分出在最后一段中的位置,然后最后一段从后向前减去
也就是二分出\(3\)的位置,把\(5\)全减一,\(4\)则从后向前减一个\(4\),变为\(4,4,4,4,4,3,3,2,1\)
很明显可以用树状数组\(+\)差分方便地维护该数组
code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define MAXN 1000005
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
using namespace std;
ll tr[MAXN];
ll a[MAXN];
ll n,m;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline bool cmp(ll x,ll y){return x>y;}
inline void modify(ll x,ll y){while (x<=n+1)tr[x]+=y,x+=x&(-x);}
inline ll query(ll x){ll y=0;while (x)y+=tr[x],x-=x&(-x);return y;}//query(x)表示第x位的值
inline ll binary(ll x){ll l=1,r=n+1,mid;while (l<r)mid=(l+r)>>1,query(mid)<=x?r=mid:l=mid+1;return l;}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=read(),m=read();fo(i,1,n)a[i]=read();sort(a+1,a+n+1,cmp);
fo(i,1,n)modify(i,a[i]),modify(i+1,-a[i]);
fo(i,1,m)
{
ll x=read(),tmp=query(x);
if (!tmp){printf("%lld\n",i-1);return 0;}
ll xx=binary(tmp),yy=binary(tmp-1);
modify(1,-1),modify(xx,1);
if (yy-(x-(xx-1))>0)modify(yy-(x-(xx-1)),-1),modify(yy,1);
}
printf("%lld\n",m);
return 0;
}