百题计划-5 codeforces 651 div2 D. Odd-Even Subsequence 二分检查
2024-10-21 11:47:21
https://codeforces.com/contest/1370/problem/D
二分检查
#include<bits/stdc++.h> using namespace std; typedef long long ll;
const int maxn=200100;
const int INF=(1LL<<30);
const ll MOD=1e9+7; int n,k;
int a[maxn];
/**
奇数位 from 1
k%2==0,不能取n 偶数位 from 2
k%2==1,不能取n
*/ bool check_odd(int m){
int cnt=(k+1)/2;
int last=0;
for(int i=1;i<=n;i++){
if(a[i]<=m) cnt--,last=i,i++;
if(cnt==0) break;
}
if(cnt==0){
if(k%2==0) return last!=n;
return 1;
}
return 0;
} bool check_even(int m){
int cnt=k/2;
int last=0;
for(int i=2;i<=n;i++){
if(a[i]<=m) cnt--,last=i,i++;
if(cnt==0) break;
}
if(cnt==0){
if(k%2) return last!=n;
return 1;
}
return 0;
} bool check(int m){
return check_odd(m) || check_even(m);
} int bin(int l,int r){
if(k==1) return l;
int res=r;
while(l<=r){
int m=(l+r)>>1;
if(check(m)) res=min(res,m),r=m-1;
else l=m+1;
}
return res;
} int main(){
while(cin>>n>>k){
int max_a=0,min_a=MOD;
for(int i=1;i<=n;i++) cin>>a[i],max_a=max(max_a,a[i]),min_a=min(min_a,a[i]);
cout<<bin(min_a,max_a)<<endl;
}
return 0;
}
最新文章
- PostgreSql性能测试
- Windows共享作为公司文件服务器的案例
- 【原创】O2O,你真的知道怎么玩吗?
- html总集
- 关于java MulticastSocket中的joinGroup(SocketAddress mcastAddr,NetworkInterface netif)
- 射频识别技术漫谈(3)&mdash;&mdash;能量、调制【worldsing 笔记】
- [RxJS] Subject basic
- java_设计模式_单例模式_Singleton Pattern(2016-08-04)
- C#中foreach遍历学习笔记
- 使用Publish Over SSH插件实现远程自动部署
- chrome浏览器和其它浏览器对scrollTop、scrollLeft的获取方法
- Jenkins+PowerShell持续集成环境搭建(五)SSRS项目
- 寒假训练——搜索 E - Bloxorz I
- Windows下安装Python扩展模块提示“Unable to find vcvarsall.bat”的问题
- Linux/shell: Concatenate multiple lines to one line
- centos7 部署elasticsearch
- ssh架构之hibernate(三)关系映射
- 11-hdfs-NameNode-HA-wtihQJM解决单点故障问题
- usbnet驱动深入分析-usb虚拟网卡host端【转】
- android tab之间滑动切换界面功能