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
代码如下：
#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;
}
求采纳。
下面是C++代码的实现：
#include <bits/stdc++.h>
using namespace std;
// 判断科丁博士是否能压过上家
bool canBeat(int n, int x, int arr[])
{
// 建立一个长度为10^9的数组
int cnt[1000];
// 把输入的n个整数映射到这个数组，如果有重复的，就把数组对应位置的值加1
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; i++)
cnt[arr[i]]++;
// 从x开始遍历数组，如果该位置的值大于等于4，则返回true
for (int i = x; i < 10; i++)
if (cnt[i] >= 4)
return true;
return false;
}
// 主函数
int main()
{
int n, x;
cin >> n >> x;
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
if (canBeat(n, x, arr))
cout << 1;
else
cout << 0;
return 0;
}