題目鏈接：點擊查看

題目大意：原本有一個1~n的排列，現在缺少了一些數字，用0來代替，現在要求將缺少的數字重新填回去，要求代價和最少，規定代價為：若相鄰兩個數字的奇偶性不同，則代價為1，否則代價為0

題目分析：因為要讓代價和最小，我們考慮貪心策略，對于每一段連續的0，我們可以視為一個數據結構，其中需要維護l，r，num，flag這四個變量，分別代表：左端的數的奇偶性，右端的數的奇偶性，包含了多少個0，是否已經被填滿，flag先不用管，我們很容易通過原數列維護出前三個變量，那么l和r無非只有下列兩種情況：

l和r的奇偶性相同

l和r的奇偶性不同

注意特判一下在兩端的區間，因為此時只有一端有約束條件，我們需要特殊處理一下

既然把所有的區間0都拿出來了，我們排一下序，因為如果填充數字的話，肯定是優先填區間長度小的，因為假如只剩下4個奇數了，現在還有三個區間0，其長度分別為2,2,4，顯然把兩個長度為2的填上更優

排好序后，稍微想一下會發現，優先填l和r奇偶性相同的更優，因為如果最后剩下的數不夠填了，那兩端奇偶性相同的區間對答案的貢獻是2，而兩端不同的以及只有一端有約束條件的區間對答案的貢獻為1，所以優先填奇偶性相同的區間

最后統計答案就好了，首先對于原數列，如果相鄰兩個數都非零，且奇偶性不同，則對答案貢獻1，和上面一起加起來就好了

注意特判一下n=1的情況，因為只有一個數，所以答案為0

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;struct Node {bool flag;//判斷是否填滿 int l,r,num;Node(int l,int r,int num):l(l),r(r),num(num){flag=false;}bool operator<(const Node& a)const{return num<a.num;} };vector<Node>zero;//儲存連續的0區間 int a[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,ans=0;scanf("%d",&n);int odd=(n+1)/2;int even=n/2;a[0]=a[n+1]=-1;for(int i=1;i<=n;i++){scanf("%d",a+i);if(a[i-1]>0&&a[i]>0)//如果前后奇偶性不同，則對答案貢獻1 ans+=(a[i-1]&1)^(a[i]&1);if(a[i]){if(a[i]&1)odd--;elseeven--;}}if(n==1)//特判n=1 return 0*printf("0\n");if(odd==(n+1)/2&&even==n/2)//特判全是0 return 0*printf("1\n");for(int i=1;i<=n;i++){if(!a[i]){int mark=i;//第一個0的位置while(i<=n&&!a[i])i++;int pre,next;if(a[mark-1]==-1)pre=-1;elsepre=a[mark-1]&1;if(a[i]==-1)next=-1;elsenext=a[i]&1;zero.push_back(Node(pre,next,i-mark));}}sort(zero.begin(),zero.end());for(int i=0;i<zero.size();i++){if(zero[i].l==zero[i].r){if(zero[i].l){if(odd>=zero[i].num){zero[i].flag=true;odd-=zero[i].num;}}else{if(even>=zero[i].num){zero[i].flag=true;even-=zero[i].num;}}}}for(int i=0;i<zero.size();i++){if(zero[i].l==-1||zero[i].r==-1){int type;if(zero[i].l!=-1)type=zero[i].l;elsetype=zero[i].r;if(type){if(odd>=zero[i].num){zero[i].flag=true;odd-=zero[i].num;}}else{if(even>=zero[i].num){zero[i].flag=true;even-=zero[i].num;}}}}for(int i=0;i<zero.size();i++){if(!zero[i].flag){if(zero[i].l==zero[i].r)ans+=2;elseans++;}}printf("%d\n",ans);return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

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

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