D. Odd-Even Subsequence(二分 + 奇偶下标的取法)
Problem - D - Codeforces
Ashish有一个大小为n的数组a。A的子序列被定义为一个序列，该序列可以通过删除一些元素(可能是不删除)从A中获得，而不改变剩余元素的顺序。考虑a的子序列s。他将s的代价定义为以下两者之间的最小值:在s的奇数指数下所有元素中的最大值。在s的偶数下标处的所有元素中的最大值。注意，元素的索引是它在s中的索引，而不是它在a中的索引。位置从1开始编号。因此，s的代价等于min(maz(s1, S3, 85，…)，max(82, S4, S6，…))。例如，{7,5,6)的代价是min(max(7,6)， max(5)) = min(7,5) = 5。帮助他找到大小为k的子序列的最小代价。输入第一行包含两个整数n和k (2 < k < n < 2- 105)——数组a的大小和子序列的大小。下一行包含n个整数a1, a2， ..， an(1≤a;≤10°)-数组a的元素。输出输出一个整数-大小为k的子序列的最小代价。
Examples
input
Copy
4 2 1 2 3 4
output
Copy
1
input
Copy
4 3 1 2 3 4
output
Copy
2
input
Copy
5 3 5 3 4 2 6
output
Copy
2
input
Copy
6 4 5 3 50 2 4 5
output
Copy
3
请注意在第一个测试中，考虑子序列s ={1,3}。这里代价等于min(max(1)， maz(3)) = 1。在第二个测试中，考虑子序列s ={1,2,4)。这里代价等于min(maz(1,4)， maz(2)) = 2。在第四个测试中，考虑子序列s ={3,50,2,4}。这里代价等于min(maz(3,2)， maz(50,4)) = 3。
题解:
我们只需要求奇数下标值和,和偶数下标之和最小的即可
对于奇数下标的取值范围
如果n%2 == 1
奇:可以取1 ~ n,注意每取一个都要至少隔一个再取,并且要取够(k+1)/2
偶:可以取2~n - 1,取够k/2
如果n%2 == 0
奇:取1~n-1,取够k/2
偶:取2~n,取够k/2
那现在我们就可以二分了,分情况讨论
看所给区间是否可以取够<mid
可以取够说明,值可以更小
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int long long
int n,k;
int a[200050];
int check(int l,int r,int x,int w)
{int cnt = 0;for(int i = l;i <= r;i++){if(a[i] < x){cnt++;i++;}}return cnt >= w;
}
int erfen(int L,int R,int w)
{int l = 1,r = 1e9;while(l <= r){int mid = (l + r)/2;if(check(L,R,mid,w)){r = mid - 1;}else{l = mid + 1;}}return l - 1;
}
void solve()
{cin >> n >> k;for(int i = 1;i <= n;i++){cin >> a[i];}int x = (k + 1)/2;int y = k/2;int ans = 0;if(x == y){ans = min(erfen(1,n - 1,x),erfen(2,n,x));}else{ans = min(erfen(1,n,x),erfen(2,n - 1,y));}cout << ans ;
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;
// cin >> t;while(t--){solve(); }
}