codevs1217 借教室 題解

題意

/中文題慣例不翻譯

箋釋

這道題確實不好過，內存方面和時間方面要求都相當嚴格呢。
思路的話無非二分人數，最小第一個人就要取消掉，最大的話m個人都能滿足，并且第i個人能滿足的話，i個人之前的一定也滿足(否則在之前就取消掉了)。
但是如何確定第i個人能否滿足呢，這道題用到的是差分數組的方法，

int check(int x) {int ans=0;//pre[i]:差分數組 里面存的是能讓ans代表第i天所需教室的數字for(int i=1;i<=n;i++){pre[i]=0;}for(int i=1;i<=x;i++){pre[s[i]]+=d[i];pre[t[i]+1]-=d[i];}for(int i=1;i<=n;i++){ans+=pre[i];if(ans>r[i]){return 0;}}return 1; }

具體想表達的感覺就已經完全被表達出來了，不知道能不能說明白呢，時常為此感到困惑。
互相理解果然是需要雙方的共同努力才行的呢，不過對于我來說，也確實存在著諸多表達方面的問題，不過自己能否理解自己呢，我想，總是要讓自己多多少少或是完完全全地理解自己才行的。

完整代碼

#include<bits/stdc++.h> #define MAXN 1000005 using namespace std; int n,m; int r[MAXN]; int d[MAXN],s[MAXN],t[MAXN]; int pre[MAXN]; int check(int x) {int ans=0;//pre[i]:差分前綴數組 里面存的是能讓ans代表第i天所需教室的數字for(int i=1;i<=n;i++){pre[i]=0;}for(int i=1;i<=x;i++){pre[s[i]]+=d[i];pre[t[i]+1]-=d[i];}for(int i=1;i<=n;i++){ans+=pre[i];// printf("%d %d\n",ans,i);if(ans>r[i]){return 0;}}return 1; } int solve() {int l=1;int r=m;while(l<=r){//printf("%d %d\n",l,r);int mid=(l+r)>>1;if(check(mid)){l=mid+1;}else{r=mid-1;}}if(l<=m){printf("-1\n%d\n",l);}else{printf("0\n");}return 0; } int main() {scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&r[i]);}for(int i=1;i<=m;i++){scanf("%d %d %d",&d[i],&s[i],&t[i]);}solve(); }

轉載于:https://www.cnblogs.com/SoniciSika/p/9034208.html

總結

以上是生活随笔為你收集整理的codevs1217 借教室 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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