首页 > 代码库 > 二分 [SWUST OJ 327] 最小的最大与最大的最小

二分 [SWUST OJ 327] 最小的最大与最大的最小

2024-07-28 18:15:55   220人阅读

最小的最大与最大的最小(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] 最小的最大与最大的最小


联系
我们