題意：
有n天，m個(gè)請(qǐng)求。n天內(nèi)每天的可用教室為a_ia?i??個(gè)，m個(gè)請(qǐng)求是從l到r天租借t個(gè)教室。 如果某一天的教室分配無法滿足，則輸出當(dāng)前的訂單號(hào)。

---

思考：

一開始根本沒想到這個(gè)東西怎么二分。。

瞄了一眼題解才發(fā)現(xiàn)自己太弱。。。

首先要找單調(diào)性，因?yàn)橹挥芯哂袉握{(diào)性質(zhì)的東西才能二分判斷可行解。

在對(duì)題目分析了之后，我們發(fā)現(xiàn)就只有 每天租借教室的數(shù)量、訂單的數(shù)量。

所以只能對(duì)訂單的數(shù)量二分，每次二分一個(gè)訂單的最大值，判斷是否可行。

可行則擴(kuò)大，不可行則縮小。

感覺usaco的題目和NOIP的題目都比較有思維的難度，一般在于題目建模與轉(zhuǎn)化，所以需要多加訓(xùn)練和思考！！！

?

#include <stdio.h> #include <algorithm> using namespace std; typedef long long ll;const int Maxn = 1000005;int Min = 0x3f3f3f3f; int Day,need; int num[Maxn]; int Rent[Maxn],Start[Maxn],End[Maxn]; ll Sum[Maxn];bool Check(int m){for(int i=0;i<=Day;++i) Sum[i] = 0;for(int i=1;i<=m;++i){Sum[Start[i]]+=Rent[i];Sum[End[i]+1]-=Rent[i];}ll now = 0;for(int i=1;i<=Day;++i){now+=Sum[i];if(now > num[i]){Min = min(Min,m);return true;}}return false; }int main(){scanf("%d%d",&Day,&need);for(int i=1;i<=Day;++i){scanf("%d",&num[i]);}for(int i=1;i<=need;++i){scanf("%d%d%d",&Rent[i],&Start[i],&End[i]);}if( !Check(need) ){printf("0\n");return 0;}else{int l = 1 , r = need+1;while( l < r){int m = (l+r)>>1;if( Check(m) ) r = m;else l = m + 1;}printf("-1\n%d\n",Min);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/OIerLYF/p/7792614.html

總結(jié)

以上是生活随笔為你收集整理的[二分][前缀和]洛谷 P1083 借教室的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。