题目链接
题目大意:
给定一个长度为n的a数组和长度为m的b数组,每个数组中的数代表着当前各个队伍有的stone的位置。选定一个位置c,如果存在一个红队的石头到c的距离小于所有蓝队的石头到c的距离,那么红队积一分,问c选最合适的地方的时候红队的最高得分是多少,如果不存在方案则输出Impossible
核心思想:
一定要注意对问题的转换,如果一直盯这C点,想通过找C点来找到最大值,那这题就做不出来了。因为C可以取任意实数,所以满足红队的石头到c的距离小于所有蓝队的石头到c的距离,这个石头就在相邻两个蓝色石头之间,我们只需要枚举每个区间取存在多少红石子的最大值就可以了。
注意:
1、可能有红队石子在蓝队最小值的最左边,也可能存在蓝队最小值的最右边,所以我们将蓝队的最小值设为负数,最大值设为正无穷。
2、如果我们遍历每一个区间,肯定会超时,所以我们可以借助upper_bound和lower_bound来得到在蓝队相邻石子之间的红队石子的左右下标,就可以直接计算个数了。
#include<bits/stdc++.h> using namespace std; int t; int n,m; int a[100005]; int b[100005]; int ans=-1; int main(){ cin>>t; while(t--){ ans=-1; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) cin>>b[i]; b[0]=-100;b[m+1]=0x3f3f3f3f; sort(a+1,a+1+n); sort(b+1,b+1+m); for(int i=1;i<=m+1;i++){ int pos1=upper_bound(a+1,a+1+n,b[i-1])-(a+1); int pos2=lower_bound(a+1,a+1+n,b[i])-(a+1); int temp=pos2-pos1; ans=max(temp,ans); } if(ans==0) cout<<"Impossible"<<endl; else cout<<ans<<endl; } return 0; }