K11308 科丁博士能出牌吗

Question

K11308 科丁博士能出牌吗
题目描述
科丁星人的进化程度远远领先于地球人，他们的扑克牌也和地球上的扑克牌不一样。科丁星的扑克牌有10^9 种牌，牌上的数字分别从1到10^9 （没有J Q K和大小王）。不像我们地球人每种牌有4张，科丁星的扑克牌每种牌有8张，也就是说科丁星的每副牌有8*10^9 张。科丁星打牌的规则也是牌面上数字越大的牌越厉害。
科丁博士很喜欢打牌，他的牌打的也很好。今天科丁博士又约了实验室的同事一起打牌。科丁博士习惯于按照从左到右，从小到大的顺序拿牌。科丁博士的这一局已经开始了一段时间，科丁博士现在手上有n张牌。科丁博士还是按照他一贯的喜好进行拿牌。科丁博士的上家出了4张x, 现在轮到科丁博士出牌了，如果科丁博士手上所有大于x的牌中有某种牌不少于4张，那么科丁博士就可以压过上家，请你帮助科丁博士算一算他手上的牌能否压过上家？ （1≤ n,≤10^6, 1≤ x,≤10^9）。

输入格式
第1行：两个整数n, x（分别代表科丁博士手上牌的数量和科丁博士上家出牌的大小）
第2到第n+1行， n个整数，分别代表科丁博士手上的牌。

输出格式
一行：如果科丁博士能压过上家输出1，否则输出0

输入输出样列
输入样例1：
6 5
1
10
10
10
10
10
输出样例1：
1
输入样例2：
5 10
1
3
10
10
10
输出样例2：
0
【耗时限制】1000ms 【内存限制】128MB

Answer 1

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[9000000];
int lower(int a[],int l,int r,int x){
    while(l<r){
        int m=(l+r)/2;
        if(a[m]>=x)    r=m;
        else if(a[m]<x)    l=m+1;
    }
    return l;
}
int upper(int a[],int l,int r,int x){
    while(l<r){
        int m=(l+r)/2;
        if(a[m]>x)    r=m;
        else if(a[m]<=x)    l=m+1;
    }
    return l;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--){
        if(upper(a,1,n+1,a[i])-lower(a,1,n+1,a[i])>=4){
            cout<<1;
            return 0;
        }
    }
    cout<<0;
    return 0;
}

求采纳。

Answer 2

谢谢！