这道题算是一道需要考虑优化算法的题了。
读题，不难发现需要求出的答案是第一个满足不了的订单，所以可以考虑二分快速查找这时，不难想到一个普素算法30分，直接暴力check不就好了。
#include<iostream> #include<cstdio> #include<ctime> #include<cstring> #include<string> #include<cmath> #include<iomanip> #include<queue> #include<deque> #include<algorithm> #include<map> #include<set> #include<vector> #include<stack> #include<bitset> #include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(int x) { if(x==0){putchar('0');putchar(' ');return;} if(x<0)putchar('-'),x=-x; int num=0;char ch[500]; while(x)ch[++num]=x%10+'0',x/=10; while(num)putchar(ch[num--]); putchar(' ');return; } const int MAXN=1000002; int n,m; int a[MAXN],b[MAXN]; int d[MAXN],x[MAXN],y[MAXN]; int check(int p) { memset(b,0,sizeof(b)); for(int i=1;i<=p;i++) { for(int j=x[i];j<=y[i];j++) { b[j]+=d[i]; if(b[j]>a[j])return 0; } } return 1; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++) { d[i]=read(); x[i]=read(); y[i]=read(); } int l=1,r=m+1; while(l+1<r) { int mid=(l+r)>>1; if(check(mid)==0)r=mid; else l=mid; } if(check(r)==1&&r==m+1){put(0);return 0;} else put(-1); if(check(l)==0){put(l);} else {put(r);} return 0; }
预期：30分，实测40分。注意二分是r边界是m+1，并非n+1,脑残的我打代码时打成了n+1。
对于70分数据我不知道为什么直接想这个是统计的可以前缀和优化，但是这个貌似不行，那树状数组可以差分一下区间修改单点查询啊，最后1~n查一遍不就好了。
#include<iostream> #include<cstdio> #include<ctime> #include<cstring> #include<string> #include<cmath> #include<iomanip> #include<queue> #include<deque> #include<algorithm> #include<map> #include<set> #include<vector> #include<stack> #include<bitset> #include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(int x) { if(x==0){putchar('0');putchar(' ');return;} if(x<0)putchar('-'),x=-x; int num=0;char ch[500]; while(x)ch[++num]=x%10+'0',x/=10; while(num)putchar(ch[num--]); putchar(' ');return; } const int MAXN=1000002; int n,m; int a[MAXN]; int d[MAXN],x[MAXN],y[MAXN]; int c[MAXN]; void add(int x,int y){for(;x<=n;x+=x&(-x))c[x]+=y;} int ask(int x) { int ans=0; for(;x;x-=x&(-x))ans+=c[x]; return ans; } int check(int p) { memset(c,0,sizeof(c)); for(int i=1;i<=p;i++) { add(x[i],d[i]); add(y[i]+1,-d[i]); } for(int i=1;i<=n;i++)if(ask(i)>a[i])return 0; return 1; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++) { d[i]=read(); x[i]=read(); y[i]=read(); } int l=1,r=m+1; while(l+1<r) { int mid=(l+r)>>1; if(check(mid)==0)r=mid; else l=mid; } if(check(r)==1&&r==m+1){put(0);return 0;} else put(-1); if(check(l)==0){put(l);} else {put(r);} return 0; }
预期70分，实测85。注意不能r写成m+1时还不能check，要不树状数组lowbit（0）疯狂TLE，而脑残的我就这样疯狂TLE了。
r写成m+1时且不check（r）时可得95分。
最后一个点的优化。。当然还是本人自己想出来的，这个很容易想，二分出来的p值一直都是从1~n的而c数组每次二分都要清0再重新赋值这不就慢很多了么。
所以可以考虑不修改，直接进行赋值即可。就是加一个逆操作，c数组不变。
#include<iostream> #include<cstdio> #include<ctime> #include<cstring> #include<string> #include<cmath> #include<iomanip> #include<queue> #include<deque> #include<algorithm> #include<map> #include<set> #include<vector> #include<stack> #include<bitset> #include<bits/stdc++.h> using namespace std; inline long long read() { long long x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(long long x) { if(x==0){putchar('0');putchar(' ');return;} if(x<0)putchar('-'),x=-x; long long num=0;char ch[500]; while(x)ch[++num]=x%10+'0',x/=10; while(num)putchar(ch[num--]); putchar(' ');return; } const long long MAXN=1000002; long long n,m; long long a[MAXN]; long long d[MAXN],x[MAXN],y[MAXN]; long long c[MAXN]; long long prev=0; void add(long long x,long long y){for(;x<=n;x+=x&(-x))c[x]+=y;} long long ask(long long x) { long long ans=0; for(;x;x-=x&(-x))ans+=c[x]; return ans; } long long check(long long p) { if(p>prev) for(long long i=prev+1;i<=p;i++) { add(x[i],d[i]); add(y[i]+1,-d[i]); } else for(long long i=prev;i>p;i--) { add(x[i],-d[i]); add(y[i]+1,d[i]); } prev=p; for(long long i=1;i<=n;i++)if(ask(i)>a[i])return 0; return 1; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(long long i=1;i<=n;i++)a[i]=read(); for(long long i=1;i<=m;i++) { d[i]=read(); x[i]=read(); y[i]=read(); } long long l=1,r=m+1; while(l+1<r) { long long mid=(l+r)>>1; if(check(mid)==0)r=mid; else l=mid; } if(r==m+1){put(0);return 0;} else put(-1); if(check(l)==0)put(l); else put(r); return 0; }
就这样成功优化成功了，要不是m打成n了，而且还check（r）了，我不用点题解也能a了这道题。。后悔