首先它就是一個陣列，主打輔助
偏向于區間的操作，因為如果我們去列舉每一個數去操作，操作次數過多且資料量大的話，這種方法容易超時，
但是我們發現，它一般區間的操作都是統一加或者減某個數等（其他神操作不贅述），然后我們可以得知，這些操作比較的單調？死板？
這樣我們其實可以去將它們轉化一下
比如差分？？？
假設我們現在有一個陣列
1 3 4 6 2 7 9 2
然后我們去求出它的差分陣列
其實就是 d[i]=a[i]-a[i-1];
則我們可以表示出來
0 2 1 2 -4 5 2 -7
其實如果我們此時修改的話，最后中間發生某個區間，假設【2，4】發生改變，但是不會影響前面與后續區間的求解（有點抽象）
舉個栗子，我們將【2，4】同時加上3，則差分陣列會變化為：
0 2+3 1 2 -4-3 5 2 -7
0 5 1 2 -7 5 2 -7
這就是改變一個區間的所有數值的操作
實質上就是 d[2]+=3,d[4+1]-=3;
詳細可以看P1083的代碼如最下面，，，
算了我不是一個好老師
直接上傻瓜式代碼
//...
//求出差分陣列
for(long i=1;i<=n;i++)
d[i]=a[i]-a[i-1];
//區間加法
for(long i=1;i<=n;i++){
cin>>left>>right>>tt;
dist[left]+=tt;
dist[right]-=tt;
}
//因為d[i]=a[i]-a[i-1]
//則a[i]=a[i-1]+d[i];
for(long i=1;i<=n;i++)
a[i]=a[i-1]+d[i];
以上只是模板套，還是得完全理解才可以去用它解決問題
現在上P1083
在大學期間，經常需要租借教室，大到院系舉辦活動，小到學習小組自習討論，都需要向學校申請借教室，教室的大小功能不同，借教室人的身份不同，借教室的手續也不一樣，
面對海量租借教室的資訊，我們自然希望編程解決這個問題，
我們需要處理接下來n天的借教室資訊，其中第ii天學校有ri?個教室可供租借，共有m份訂單，每份訂單用三個正整數描述，分別為dj?,sj?,tj?，表示某租借者需要從第sj?天到第tj?天租借教室（包括第sj?天和第tj?天），每天需要租借dj?個教室，
我們假定，租借者對教室的大小、地點沒有要求，即對于每份訂單，我們只需要每天提供dj?個教室，而它們具體是哪些教室，每天是否是相同的教室則不用考慮，
借教室的原則是先到先得，也就是說我們要按照訂單的先后順序依次為每份訂單分配教室，如果在分配的程序中遇到一份訂單無法完全滿足，則需要停止教室的分配，通知當前申請人修改訂單，這里的無法滿足指從第sj?天到第tj?天中有至少一天剩余的教室數量不足dj?個，
現在我們需要知道，是否會有訂單無法完全滿足，如果有，需要通知哪一個申請人修改訂單，
輸入格式
第一行包含兩個正整數n,m，表示天數和訂單的數量，
第二行包含n個正整數，其中第i個數為ri?，表示第i天可用于租借的教室數量，
接下來有m行，每行包含三個正整數dj,sj,tj 表示租借的數量，租借開始、結束分別在第幾天，
每行相鄰的兩個數之間均用一個空格隔開，天數與訂單均用從11開始的整數編號，
輸出格式
如果所有訂單均可滿足，則輸出只有一行，包含一個整數0，否則（訂單無法完全滿足）
輸出兩行，第一行輸出一個負整數-1，第二行輸出需要修改訂單的申請人編號，
輸入輸出樣例
輸入 #14 3
2 5 4 3
2 1 3
3 2 4
4 2 4
輸出 #1
-1
2
說明/提示
【輸入輸出樣例說明】
第 11份訂單滿足后，44天剩余的教室數分別為 0,3,2,3，第 2 份訂單要求第 2天到第 4天每天提供3個教室，而第 3 天剩余的教室數為2，因此無法滿足，分配停止，通知第2 個申請人修改訂單，
【資料范圍】
對于10%的資料，有1≤ n,m≤ 10；
對于30%的資料，有1≤ n,m≤1000；
對于 70%的資料，有1≤n,m≤105；
對于 100%的資料，有1≤n,m≤106,0≤ri?,dj?≤109,1≤sj?≤tj?≤n，
NOIP 2012 提高組 第二天 第二題
它是一個二分加差分陣列，請各位看官小心食用，，，
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long n,m;
long long r[1000010];
long long d[1000010],s[1000010],t[1000010];
long long dist[1000010];
long long k[1000010];
bool check(long u){
memset(dist,0,sizeof(dist));
for(long i=1;i<=u;i++)
{
dist[s[i]]+=d[i];
dist[t[i]+1]-=d[i];
}
for(long i=1;i<=n;i++)
{
k[i]=k[i-1]+dist[i];
if(k[i]>r[i]) return 0;
}
return 1;
}
int main(){
scanf("%lld %lld",&n,&m);
for(long i=1;i<=n;i++)
scanf("%lld",&r[i]);
for(long i=1;i<=m;i++)
scanf("%lld %lld %lld",&d[i],&s[i],&t[i]);
long l=1,g=m;
if(check(m)) {
printf("0");return 0;}
while(l<g){
long mid=(l+g)>>1;
if(check(mid)) l=mid+1;
else g=mid;
}
printf("-1\n%ld",l);
}
/*筆記記錄：
前綴和 假設有 2 3 0 -2 -3 則后面的不會被前面影響
它在中間就被抵消了 即前面發生的不會影響后面的
這就是差分嗎愛了愛了
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21328.html
標籤：其他