P1083 [NOIP 2012 提高组] 借教室 题解
题目
题目传送门。
题解
思路
这一题可以使用差分优化+二分答案法做。
二分查找一个值\(x\)，代表前\(x\)个订单是否满足条件，每次在循环中调用一个函数\(check(int\ x)\)，用于检测前\(x\)个订单是否可以满足。
\(check\)函数细节思路：使用差分数组\(c\)存档前\(e_i+1_{max}\)天的租借教室情况，后面存档完毕后再将\(c\)进行前缀和，这样就得出了最终租借教室每天的租借数量了。随后就是for循环比较，如果有任意一天超过了预期\(r_i\)就返回false（代表不满足条件）最后返回true（代表前\(x\)个订单可以完全满足）。
在二分循环内，若\(check\)返回false，代表无法承受前\(x\)个订单的租借，于是得减小租借量（\(r=mid\)），否则就是可以完全满足，要尽可能满足更多的订单，所以需要把\(l\)赋值为\(mid\)。
代码
#include<bits/stdc++.h>
#define endl '\n'using namespace std;long long n,m,r[1000005],d[1000005],s[1000005],e[1000005],c[1000005];
inline bool check(long long x){ memset(c,0,sizeof c);long long mxe=-1;for(long long i=1;i<=x;i++){c[s[i]]+=d[i];c[e[i]+1]-=d[i];mxe=max(mxe,e[i]+1);} for(long long i=1;i<=mxe;i++){c[i]=c[i-1]+c[i];}for(long long i=1;i<=mxe;i++){if(c[i]>r[i]) return 0;}return 1;
}
int main(){cin>>n>>m;for(long long i=1;i<=n;i++) cin>>r[i];for(long long i=1;i<=m;i++) cin>>d[i]>>s[i]>>e[i];long long l=0,r=m+1;while(l+1<r){long long mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;}if(l==m) cout<<0<<endl;else cout<<-1<<endl<<l+1<<endl;return 0;
}
总结
注意：如果你在第21个测试点WA了，请检查你的数据类型是否设置为long long。
这道题考察的知识面较广，很适合同学们锻炼思维用。