題面

傳送門

題目大意：

有一個長n(n為偶數)的序列a

已知a滿足 \(a_1≤a_2≤?≤a_n\)

給出一個長度為\(\frac{n}{2}\) 的序列b，定義\(b_i=a_i+a_{n-i+1}\)

求出序列a (輸出任意一種答案即可)

分析

為了保證序列不下降，我們采用貪心的思想，先假設\(a_i=a_{i-1}\),這樣給后面的數留有的余地更大

然后計算出\(a_{n-i+1}=b_i-a_i\)，如果\(a_{n-i+1}>a_{n-i+1+1}\),即不滿足不下降的條件，則進行局部調整

令\(a_{n-i+1}=a_{n-i+1+1}\)，重新計算\(a_i=b_i-a_{n-i+1}\) (注，設$a_{n+1}=+\inf $)

由于\(a_{n-i+1}>a_{n-i+2}\)，新的\(a_i\)的值會變大，依然滿足不下降的條件

該方法的正確性顯然，時間復雜度\(O(n)\)

代碼

#include<iostream> #include<cstdio> #define maxn 200005 #define INF 0x7fffffffffffffff using namespace std; int n; long long a[maxn]; long long b[maxn]; int main(){scanf("%d",&n);for(int i=1;i<=n/2;i++) scanf("%I64d",&b[i]);a[n+1]=INF; for(int i=1;i<=n/2;i++){a[i]=a[i-1];a[n+1-i]=b[i]-a[i];if(a[n+2-i]<a[n+1-i]){a[n+1-i]=a[n+2-i];a[i]=b[i]-a[n+1-i];}} for(int i=1;i<=n;i++){printf("%I64d ",a[i]);} }

轉載于:https://www.cnblogs.com/birchtree/p/10126769.html

總結

以上是生活随笔為你收集整理的Codeforces 1093C (思维+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

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