問題描述
在一條街上有n個賣菜的商店，按1至n的順序排成一排，這些商店都賣一種蔬菜。 第一天，每個商店都自己定了一個正整數的價格。店主們希望自己的菜價和其他商店的一致，第二天，每一家商店都會根據他自己和相鄰商店的價格調整自己的價格。具體的，每家商店都會將第二天的菜價設置為自己和相鄰商店第一天菜價的平均值（用去尾法取整）。 注意，編號為1的商店只有一個相鄰的商店2，編號為n的商店只有一個相鄰的商店n-1，其他編號為i的商店有兩個相鄰的商店i-1和i+1。 給定第二天各個商店的菜價，可能存在不同的符合要求的第一天的菜價，請找到符合要求的第一天菜價中字典序最小的一種。 字典序大小的定義：對于兩個不同的價格序列(a1, a2, ..., an)和(b1, b2, b3, ..., bn)，若存在i (i>=1), 使得ai<bi，且對于所有j<i，aj=bj，則認為第一個序列的字典序小于第二個序列。
輸入格式
輸入的第一行包含一個整數n，表示商店的數量。 第二行包含n個正整數，依次表示每個商店第二天的菜價。
輸出格式
輸出一行，包含n個正整數，依次表示每個商店第一天的菜價。
樣例輸入
8 2 2 1 3 4 9 10 13
樣例輸出
2 2 2 1 6 5 16 10
數據規模和約定
對于30%的評測用例，2<=n<=5，第二天每個商店的菜價為不超過10的正整數； 對于60%的評測用例，2<=n<=20，第二天每個商店的菜價為不超過100的正整數； 對于所有評測用例，2<=n<=300，第二天每個商店的菜價為不超過100的正整數。 請注意，以上都是給的第二天菜價的范圍，第一天菜價可能會超過此范圍。
解析：
由于是去尾法取整，所以這題的每組相鄰的商店菜價總和是由區間限制的，可以利用差分約束來做。差分約束有一般有兩種求解方式，求最大值，求最小值。這里求字典序最小即要求最小值，可以利用spfa()求最長路徑（不理解的戳這里）。建圖還是采用我個人最喜歡的鏈式向前星（不懂戳這里）。
PS：鏈接里的大概意思是，求最長路的松弛操作是if (dist[end]<dist[sta]+邊權值){ dist[end]=dist[sta]+權值; },求出的dist[end]的解是滿足約束條件(>=dist[sta]+權值)中最小的（因為取的是等號，還可能存在比這個更大的解）。求最大值的原理類似。
1 #include <iostream> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5 struct Edge{ 6 int to; 7 int next;//與當前邊起點一樣的另一條邊的位置 8 int v; 9 }edge[2006]; //鏈式向前星：每個節點存一條邊; 10 int n=0,cur=0; //cur當前已有邊的個數 11 int a[305],dist[306],vis[305],head[305],inq[305]; 12 //head[i]以i為起點的邊最大的編號 13 void addedge(int from,int to,int w) 14 { 15 edge[cur].next=head[from]; 16 edge[cur].to=to; 17 edge[cur].v=w;//路徑權值 18 head[from]=cur++;//當前節點變為頭結點 19 } 20 void spfa()//求最長路 21 { 22 queue<int> q; 23 for(int i=0;i<n+1;++i) 24 { 25 q.push(i); 26 vis[i]=1; 27 dist[i]=0; 28 inq[i]=1; 29 } 30 while(!q.empty()) 31 { 32 int x=q.front(); 33 q.pop(); 34 inq[x]++; 35 vis[x]=0; 36 if(inq[x]>n){//訪問某一節點過多，存在正環，無解 37 cout<<"no answer"<<endl; 38 return ; 39 } 40 for(int i=head[x];i!=-1;i=edge[i].next)//遍歷與該節點相連的各邊 41 { 42 int nx=edge[i].to; 43 if(dist[nx]<dist[x]+edge[i].v) 44 { 45 dist[nx]=dist[x]+edge[i].v; 46 if(!vis[nx]){ 47 vis[nx]=1; 48 q.push(nx); 49 } 50 } 51 } 52 } 53 return ; 54 } 55 int main() 56 { //解除cin cout 的綁定，提高輸入輸出效率；這個可以當模板記住，當然直接用scanf和print也可以。 57 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 58 memset(head,-1,sizeof(head));//head 全部初始為-1 59 cin>>n; 60 for(int i=1;i<n+1;++i) 61 cin>> a[i];//第二天的菜價 62 for(int i=0;i<n-2;++i) 63 { 64 addedge(i+3,i,-(a[i+2]*3+2));//從第一個三個相鄰開始，直到最后一個三個三個相鄰 65 addedge(i,i+3,a[i+2]*3); 66 } 67 //首末兩個相鄰，特殊處理 68 addedge(2,0,-(a[1]*2+1)); 69 addedge(0,2,a[1]*2); //首兩個 70 addedge(n,n-2,-(a[n]*2+1)); 71 addedge(n-2,n,a[n]*2); //結尾兩個 72 for(int i=1;i<n+1;++i) 73 { 74 addedge(i-1,i,1); //每個菜價都要大于1 75 } 76 spfa(); 77 a[1]=dist[1]; 78 for(int i=2;i<n+1;++i) 79 a[i]=dist[i]-dist[i-1]; 80 cout<<a[1]; 81 for(int i=2;i<n+1;++i) 82 cout<<' '<<a[i]; 83 cout<<endl; 84 return 0; 85 }
?(｀･ω･′)ゞ敬禮っ
