問題描述

在一條街上有n個賣菜的商店，按1至n的順序排成一排，這些商店都賣一種蔬菜。 　　第一天，每個商店都自己定了一個正整數(shù)的價格。店主們希望自己的菜價和其他商店的一致，第二天，每一家商店都會根據(jù)他自己和相鄰商店的價格調(diào)整自己的價格。具體的，每家商店都會將第二天的菜價設(shè)置為自己和相鄰商店第一天菜價的平均值（用去尾法取整）。 　　注意，編號為1的商店只有一個相鄰的商店2，編號為n的商店只有一個相鄰的商店n-1，其他編號為i的商店有兩個相鄰的商店i-1和i+1。 　　給定第二天各個商店的菜價，可能存在不同的符合要求的第一天的菜價，請找到符合要求的第一天菜價中字典序最小的一種。 　　字典序大小的定義：對于兩個不同的價格序列(a₁, a₂, ..., a_n)和(b₁, b₂, b₃, ..., b_n)，若存在i (i>=1), 使得a_i<b_i，且對于所有j<i，a_j=b_j，則認(rèn)為第一個序列的字典序小于第二個序列。

輸入格式

輸入的第一行包含一個整數(shù)n，表示商店的數(shù)量。 　　第二行包含n個正整數(shù)，依次表示每個商店第二天的菜價。

輸出格式

輸出一行，包含n個正整數(shù)，依次表示每個商店第一天的菜價。

樣例輸入

8 2 2 1 3 4 9 10 13

樣例輸出

2 2 2 1 6 5 16 10

數(shù)據(jù)規(guī)模和約定

對于30%的評測用例，2<=n<=5，第二天每個商店的菜價為不超過10的正整數(shù)； 　　對于60%的評測用例，2<=n<=20，第二天每個商店的菜價為不超過100的正整數(shù)； 　　對于所有評測用例，2<=n<=300，第二天每個商店的菜價為不超過100的正整數(shù)。 　　請注意，以上都是給的第二天菜價的范圍，第一天菜價可能會超過此范圍。

解析：

　　由于是去尾法取整，所以這題的每組相鄰的商店菜價總和是由區(qū)間限制的，可以利用差分約束來做。差分約束有一般有兩種求解方式，求最大值，求最小值。這里求字典序最小即要求最小值，可以利用spfa()求最長路徑（不理解的戳這里）。建圖還是采用我個人最喜歡的鏈?zhǔn)较蚯靶?#xff08;不懂戳這里）。

　　PS：鏈接里的大概意思是，求最長路的松弛操作是if (dist[end]<dist[sta]+邊權(quán)值){ dist[end]=dist[sta]+權(quán)值; },求出的dist[end]的解是滿足約束條件(>=dist[sta]+權(quán)值)中最小的（因為取的是等號，還可能存在比這個更大的解）。求最大值的原理類似。

1 #include <iostream> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5 struct Edge{ 6 int to; 7 int next;//與當(dāng)前邊起點一樣的另一條邊的位置 8 int v; 9 }edge[2006]; //鏈?zhǔn)较蚯靶?#xff1a;每個節(jié)點存一條邊; 10 int n=0,cur=0; //cur當(dāng)前已有邊的個數(shù) 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;//路徑權(quán)值 18 head[from]=cur++;//當(dāng)前節(jié)點變?yōu)轭^結(jié)點 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){//訪問某一節(jié)點過多，存在正環(huán)，無解 37 cout<<"no answer"<<endl; 38 return ; 39 } 40 for(int i=head[x];i!=-1;i=edge[i].next)//遍歷與該節(jié)點相連的各邊 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 的綁定，提高輸入輸出效率；這個可以當(dāng)模板記住，當(dāng)然直接用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); //結(jié)尾兩個 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 }

?(｀･ω･′)ゞ敬禮っ

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

總結(jié)

以上是生活随笔為你收集整理的CCF 差分约束--201809再卖菜的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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