怎么做装球的网站,浏览器的网站,上海建筑企业,创建一个网站买卖D. Odd-Even Subsequence 题目大意#xff1a;在a数组中 保留k个数字#xff0c;如何代价最小的多少。 代价的算法 具体看题意#xff1a;就是k数组中 min{max{奇数下标}#xff0c;max{偶数下标}}
解题思路#xff1a;贪心加二分#xff0c;二分全部的答案#xff08…D. Odd-Even Subsequence 题目大意在a数组中 保留k个数字如何代价最小的多少。 代价的算法 具体看题意就是k数组中 min{max{奇数下标}max{偶数下标}}
解题思路贪心加二分二分全部的答案即代价然后检查能不能达到这个代价。
检查的思路: 我们只要 奇数下标或者偶数下标中 所以的数都小于mid值就能达到这个代价。 所以我们分为奇数下标和偶数下标来检查。 贪心策略如果我们在检查奇数下标的时候那么我们从索引1开始往后看,一旦发现这个数小于mid就赶快拿下来保证全部小于mid然后下一个数一点是作为偶数下标的数无论这个数多大这样让后面奇数的选择更多。这个贪心策略是最优的因为你下一个数只能作为偶数下标的数了两个数相邻这样给了后面的数更多的可能成为奇数下标的数。 偶数同理。
代码
#includecstdio
using namespace std;
int N,K;
int A[217];
main()
{scanf(%d%d,N,K);for(int i0;iN;i)scanf(%d,A[i]);int L0,R1e9;while(R-L1){int MLR1;bool okfalse;for(int tm0;tm2;tm){int wttm;int cnt0;for(int i0;iN;i){if(wt1){wt0;cnt;}else if(A[i]M){wt1;cnt;}}if(cntK)oktrue;}if(ok)RM;else LM;}printf(%d\n,R);
}
