为什么我的二分总有细微的答案偏差啊????????????????/
查看原帖
为什么我的二分总有细微的答案偏差啊????????????????/
294562
EDqwq楼主2021/3/12 20:57
/*
  Author: EnderDeer
  Online Judge: Luogu
*/

#include<bits/stdc++.h>

#define int long long
#define mem(x) memset(x,0,sizeof(x))

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

int n,m;
int a[1000010];
int l,r,mid;
int ans = 11451919810;

bool check(int x){
	int cnt = 0;
	for(int i = 1;i <= n;i ++){
		if(i % 2 == 0){
			if(a[i] <= x)cnt ++;
		}
		else cnt ++;
	}
	if(cnt >= m)return true;
	cnt = 0;
	for(int i = 1;i <= n;i ++){
		if(i % 2 == 1){
			if(a[i] <= x)cnt ++;
		}
		else cnt ++;
	}
	if(cnt >= m)return true;
	return false;
}

signed main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i ++)a[i] = read(),r = max(r,a[i]);
	l = 1;
	while(l <= r){
		mid = (l + r) / 2;
		if(check(mid)){
			r = mid - 1;
			ans = mid;
		} 
		else l = mid + 1;
	}
	cout<<ans;
	return 0;
}

px

2021/3/12 20:57
加载中...