D. Odd-Even Subsequence

題目大意：在a數組中 保留k個數字，如何代價最小的多少。
代價的算法 具體看題意：就是k數組中 min{max{奇數下標}，max{偶數下標}}

解題思路：貪心加二分，二分全部的答案（即代價），然后檢查能不能達到這個代價。

檢查的思路: 我們只要 奇數下標或者偶數下標中 所以的數都小于mid值就能達到這個代價。
所以我們分為奇數下標和偶數下標來檢查。
貪心策略：如果我們在檢查奇數下標的時候，那么我們從索引1開始往后看,一旦發現這個數小于mid就趕快拿下來（保證全部小于mid），然后下一個數一點是作為偶數下標的數，無論這個數多大，這樣讓后面奇數的選擇更多。這個貪心策略是最優的，因為你下一個數只能作為偶數下標的數了（兩個數相鄰），這樣給了后面的數更多的可能成為奇數下標的數。
偶數同理。

代碼：

#include<cstdio> using namespace std; int N,K; int A[2<<17]; main() {scanf("%d%d",&N,&K);for(int i=0;i<N;i++)scanf("%d",&A[i]);int L=0,R=1e9;while(R-L>1){int M=L+R>>1;bool ok=false;for(int tm=0;tm<2;tm++){int wt=tm;int cnt=0;for(int i=0;i<N;i++){if(wt==1){wt=0;cnt++;}else if(A[i]<=M){wt=1;cnt++;}}if(cnt>=K)ok=true;}if(ok)R=M;else L=M;}printf("%d\n",R); }

總結

以上是生活随笔為你收集整理的Codeforces Round #651 (Div. 2) D的全部內容，希望文章能夠幫你解決所遇到的問題。

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