原題題意
給出長度為n的有序數組，m次詢問，每次給出一個正整數x。你要删除數組中最少的元素，使得數組中的字首和+x都為非負整數。允許離線，n≤750，m≤200,000。
原題思路
首先注意到，x能成功通過測試當且僅當字首和中最小的數≥x。
将詢問從大到小排個序，對于一個新的詢問，每次嘗試從數組中删除最優的一個數，使得成功的機會更大。
何為最優？我們注意到，ai隻會對後面的數造成影響。設目前字首和最小為now，fi為前i個字首和中最小的數，則答案會增加 max { min { now-ai , fi-1 } } （請注意後面的f囊括了now-ai顧及不到的情況）。
每次判斷最小的數在哪，暴力更新，O(n3+mlogm)。
代碼
1 #pragma GCC optimize(2)
2 #include<bits/stdc++.h>
3 using namespace std;
4 typedef long long int ll;
5 const ll inf=1000000000000000000;
6 const ll maxn=1E6+5;
7 template<typename T> void read(T &x){
8 x=0;char ch=getchar();int fh=1;
9 while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
10 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11 x=x*fh;
12 }
13 void write(ll x)
14 {
15 if(x==0){putchar('0');putchar('\n');return;}
16 if(x<0){putchar('-');x=-x;}
17 ll a[25],size=0;
18 while(x){a[++size]=x%10;x/=10;}
19 for(int i=size;i>=1;--i)putchar(a[i]+'0');
20 putchar('\n');
21 }
22 ll min(ll x,ll y){return x<y?x:y;}
23 ll max(ll x,ll y){return x>y?x:y;}
24 ll n,m,a[maxn],tot,sum[maxn],ans[maxn],f[maxn];
25 struct query{ll pos,x;}Q[maxn];
26 bool cmp(query a,query b){return a.x>b.x;}
27 ll get()
28 {
29 ll ans=inf;
30 for(int i=1;i<=n;++i)
31 {
32 sum[i]=sum[i-1]+a[i];
33 ans=min(ans,sum[i]);
34 f[i]=min(f[i-1],sum[i]);
35 }
36 return ans;
37 }
38 int main()
39 {
40 read(n);read(m);
41 for(int i=1;i<=n;++i)
42 {
43 read(a[i]);
44 if(a[i]<0)++tot;
45 }
46 for(int i=1;i<=m;++i)
47 {
48 read(Q[i].x);
49 Q[i].pos=i;
50 }
51 sort(Q+1,Q+m+1,cmp);
52 int pos=1;
53 for(int i=1;i<=tot;++i)
54 {
55 ll g=get();
56 while(Q[pos].x+g>=0&&pos<=m){ans[Q[pos].pos]=i-1;++pos;}
57 if(g>=0)break;
58 ll ans=-inf,pos=0;
59 for(int j=1;j<=n;++j)
60 {
61 if(min(g-a[j],f[j-1])>ans)
62 {
63 ans=min(g-a[j],f[j-1]);
64 pos=j;
65 }
66 }
67 a[pos]=0;
68 }
69 ll g=get();
70 while(Q[pos].x+g>=0&&pos<=m){ans[Q[pos].pos]=tot;++pos;}
71 for(int i=1;i<=m;++i)write(ans[i]);
72 return 0;
73 } View Code
EX版本：
m,n≤1,000,000，強制線上。
思路
考慮從後往前貪心。我們先隻考慮兩種情況（0顯然沒必要考慮）。
第一種，所有的數均為負數。則每次答案必然會從最小的數删起，直到删的數的絕對值第一次大于等于詢問。
第二種，隻有一個數為正，其餘均為負。兩種情況：
第一種，加起來為仍為正，那麼就不會删數。并且這一位不會對以後造成任何影響（既然都加上正數了，能到達這一位，以後肯定不會小于零）。
第二種，加起來為負。那麼會貪心地選擇最小的負數删，直到加起來為正。換個角度，會貪心地選擇最大的負數加到正數上，直到正數為負。這樣，化歸為第一情況。
再将負數加入大根堆，正數不要的原因同第一種。
圖畫畫，手算算至少能夠了解。
最後得到的答案要麼剩下正數，要麼全是負數。這些負數取反後，從大到小排序的第i位代表了取到第i種答案，要删去1~i個數。
二分查找即可。
代碼
1 #pragma GCC optimize(2)
2 #include<bits/stdc++.h>
3 using namespace std;
4 typedef long long int ll;
5 const ll inf=1000000000000000000;
6 const ll maxn=1E6+5;
7 ll min(ll x,ll y){return x<y?x:y;}
8 ll max(ll x,ll y){return x>y?x:y;}
9 template<typename T> void read(T &x){
10 x=0;char ch=getchar();int fh=1;
11 while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
12 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13 x=x*fh;
14 }
15 void write(ll x)
16 {
17 if(x==0){putchar('0');putchar('\n');return;}
18 if(x<0){putchar('-');x=-x;}
19 ll a[25],size=0;
20 while(x){a[++size]=x%10;x/=10;}
21 for(int i=size;i>=1;--i)putchar(a[i]+'0');
22 putchar('\n');
23 }
24 ll n,m,a[maxn],wait[maxn],size,x;
25 priority_queue<ll>Q;
26 int main()
27 {
28 read(n);read(m);
29 for(int i=1;i<=n;++i)read(a[i]);
30 for(int i=n;i>=1;--i)
31 {
32 while(a[i]>=0&&!Q.empty())
33 {
34 a[i]+=Q.top();
35 Q.pop();
36 }
37 if(a[i]<0)Q.push(a[i]);
38 }
39 while(!Q.empty())
40 {
41 wait[++size]=Q.top();
42 Q.pop();
43 }
44 for(int i=1;i<=size/2;++i)swap(wait[i],wait[size-i+1]);
45 for(int i=1;i<=size;++i)wait[i]+=wait[i-1];
46 for(int i=1;i<=size;++i)wait[i]=-wait[i];
47 while(m--)
48 {
49 read(x);
50 write(lower_bound(wait,wait+size+1,wait[size]-x)-wait);
51 }
52 return 0;
53 } View Code
轉載于:https://www.cnblogs.com/GreenDuck/p/10603543.html