首页 > 代码库 > 二分 [SWUST OJ 327] 最小的最大与最大的最小
二分 [SWUST OJ 327] 最小的最大与最大的最小
最小的最大与最大的最小(0327)
Time limit(ms): 2500 Memory limit(kb): 65535 Submission: 329 Accepted: 18
Description
又是一个数据处理题(>_<)。还是直接看Input吧。
Input
一组测试实例。 Line 1:两个数n, m (1 <= n <= 1000000, 1 <= m <= 100000),n表示数字个数,m表示查询次数。 Line 2:包含n个整数A(i)(0 <= A(i) <= 1000000000)。两个数之间以空格隔开。 接下来m行:每行包含两个整数a,b(1 <= a <= 2, -1000000000 <= b <= 1000000000)。表示一次查询。当a = 1时,输出n个数中比b小的数的最大值。当a = 2时,输出n个数中比b大的数的最小值。如果不存在满足条件的数,则输出-1。
Output
每于每一次查询,输出答案,每个答案占一行。
Sample Input
1 2 3 4 5 | 5 2 1 2 3 3 5 1 3 2 5 |
Sample Output
1 2 3 | 2 -1 |
Hint
SCPC_Zhangjian
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define INF 0x7fffffff#define N 1000010 int n,m;int a[N]; int low_bound(int k){ int l=1,r=n+1; while(l<r) { int m=l+(r-l)/2; if(a[m]>=k) r=m; else l=m+1; } return l;}int up_bound(int k){ int l=1,r=n+1; while(l<r) { int m=l+(r-l)/2; if(a[m]<=k) l=m+1; else r=m; } return l;} int main(){ int i,j,x; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } sort(a+1,a+n+1); //逗比了、没排序、一直WA、受不了= = while(m--) { int op,x; scanf("%d%d",&op,&x); if(op==1 && a[1]>=x || op==2 && a[n]<=x) { cout<<-1<<endl; continue; } if(op==1) { int ans=low_bound(x); ans--; cout<<a[ans]<<endl; } else { int ans=up_bound(x); cout<<a[ans]<<endl; } } return 0;}
二分 [SWUST OJ 327] 最小的最大与最大的最小
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。