Description

一開始有n個非負整數hi，接下來會進行m次操作，第i次操作給出一個數c[i]，要求你選出c[i]個大于零的數并將它們減去1。
問最多可以進行多少輪操作后無法操作（即沒有c[i]個大于零的數）

Input

第一行兩個數表示n和m
第二行n個數描述h[i]
第三行m個數描述c[i]

Output

一行表示答案，即最多可以進行多少輪操作后無法操作

Sample Input

輸入1：

3 5
1 2 5
1 2 3 2 1

輸入2：

5 5
1 3 3 4 5
1 2 4 4 4

Sample Output

輸出1：

3

輸出2：

5

Data Constraint

對于10%的數據滿足,1<=n,m<=5
對于另外20%的數據滿足，1<=n<=8，1<=h[i]<=7
對于50%的數據滿足，1<=n,m<=1000
對于80%的數據滿足,1<=n,m<=100000
對于100%的數據滿足，1<=n,m<=1000000

Solution

• 雖然數據有點大，還是決定線段樹……

• 顯然，選擇的 c 個數一定選最大的那 c 個。

• 為了方便處理，先把數組排序，中途維護時也保證單調。

• 區間減，如果第 n?c+1 個數屬于一段相同的數，就把相同的那段移到前面減（保證單調）。

• 時間復雜度 O(N?log?N) 。

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=1e6+2; struct data {int mx,c; }f[N<<2]; int ans; int a[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int max(int x,int y) {return x>y?x:y; } inline void modify(int v) {if(f[v].c){int ls=v<<1,rs=ls|1;f[ls].c+=f[v].c;f[rs].c+=f[v].c;f[ls].mx-=f[v].c;f[rs].mx-=f[v].c;f[v].c=0;} } inline void make(int v,int l,int r) {if(l==r){f[v].mx=a[l];return;}int mid=(l+r)>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);f[v].mx=max(f[v<<1].mx,f[v<<1|1].mx); } inline void change(int v,int l,int r,int x,int y) {if(l==x && r==y){f[v].c++;f[v].mx--;return;}modify(v);int mid=(l+r)>>1;if(y<=mid) change(v<<1,l,mid,x,y); elseif(x>mid) change(v<<1|1,mid+1,r,x,y); else{change(v<<1,l,mid,x,mid);change(v<<1|1,mid+1,r,mid+1,y);}f[v].mx=max(f[v<<1].mx,f[v<<1|1].mx); } inline int findnum(int v,int l,int r,int x) {modify(v);if(l==r) return f[v].mx;int mid=(l+r)>>1;int t=x<=mid?findnum(v<<1,l,mid,x):findnum(v<<1|1,mid+1,r,x);f[v].mx=max(f[v<<1].mx,f[v<<1|1].mx);return t; } inline int findpos(int v,int l,int r,int x) {modify(v);if(l==r) return l;int mid=(l+r)>>1;int t=f[v<<1].mx>=x?findpos(v<<1,l,mid,x):findpos(v<<1|1,mid+1,r,x);f[v].mx=max(f[v<<1].mx,f[v<<1|1].mx);return t; } int main() {int n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n);make(1,1,n);for(ans=0;ans<m;ans++){int x=read(),t=findnum(1,1,n,n-x+1);if(t<=0) break;int pos2=findpos(1,1,n,t);if(pos2<n-x+1){int pos1=findpos(1,1,n,t+1);if(pos1<=n && findnum(1,1,n,pos1)<=t) pos1++;if(pos1<=n) change(1,1,n,pos1,n);if(pos2+pos1-(n-x+1)-1<=n && pos2+pos1-(n-x+1)-1>=pos2) change(1,1,n,pos2,pos2+pos1-(n-x+1)-1);}else change(1,1,n,n-x+1,n);}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5431. 【NOIP2017提高A组集训10.28】序列操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。