首页 > 代码库 > noip模拟赛:部队[技巧?思想?]

noip模拟赛:部队[技巧?思想?]

王国军总指挥——卡西乌斯准将决定重建情报局,需要从全国各地挑选有能力的士兵,选择的标准为A,B两种能力。对于每个候选士兵,如果存在另一名士兵的两项能力均大于等于他,那么他将被淘汰。(注意:若两名士兵两项能力均相等,则认为排在后面被淘汰)。

 

可以认为,能力差别不大的士兵更适合在一个队伍中。(我们这样定义能力差别:设士兵iA,B能力值为aibi,士兵jA,B能力值为ajbj,那么他们的能差别为|ai-aj|+|bi-bj|

对于每个未被淘汰的士兵,只要某队伍中有另一个和他能力差别不大于k的士兵,他就可以加入该队伍。

现在,卡西乌斯想在符合以上条件的前提下,挑选出人数最多的队伍担当重任。

 

输入:第1: 2个用空格隔开的整数:n和k ,其中n表示候选士兵总数,k如题意所述。

2..n+1i+1行用2个以空格隔开整数aibi分别表示第i个士兵A,B两种能力的能力值。 

 

输出:只有1个整数,表示最多人数。

 

样例输入:5 3

2 11

4 10

3 9

1 12

6 8

 

样例输出:3

 数据范围:20% 的数据1<=n<=1000

               40% 的数据 未被淘汰的士兵总数不会多于3000人。

               100%的数据.1<=n<=100000,其余数据在[0,100000000]

 

感觉这题挺好的...无论是思想还是方法

题解应该说复杂了,其实这题想明白了就是傻逼题(哪题想明白了不是傻逼题?)...并没有必要用上并查集

 

先说说这题要我们解决的第一个问题:如果判断哪些点是可以留下来的?

根据题意,我们知道要满足没有任何一个点的横坐标和纵坐标大于等于那个点,那个点就可以留下来

要判断这两个条件看起来似乎很难,除非你打暴力我没话说

我们可以先考虑一维的情况,我们当然知道是排序一遍即可;

其实二维的也一样,我们把所有的点按照x坐标排序(假设是按从大到小排序好了)

我们可以确定,前面的点一定不可能被后面的点淘汰对吧(因为前面的x比后面的点的x大,如果是等于的情况,可任意删掉一个点,可以删掉后面的点为准)

现在的问题是,我们如何判断后面的点的y也小于前面的点的y

其实也很简单,我们不断更新最大的y,比较后面的点和当前最大y的大小即可;

 

接下来,第二个问题,如果判断集合最多的人数呢?

我们试着在纸上画出所有留下来的点,会发现什么神奇的性质呢?

所有的点形成的直线,是一条下降的曲线!(按x从大到小排序的情况,而且留下来的点,y是呈逐渐递增的)

这个性质有什么用呢?

我们整理一下留下来的点(还是按x从大到小排序)

如果后面的点,一定不和它前面一个点的距离满足小于等于k,那么我们是不是就可以知道它一定不在前面的集合里?它后面的点更不可能在前面的集合了(自己仔细想想就知道了)

那这样是不是直接扫一遍,不断更新最大的集合的个数就可以了

 

附上代码:(代码本身是按x从小到大排序,反正没有太大的区别)

 

#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>#include<queue>#include<cmath>#include<map>#include<set>#include<cstdlib>using namespace std;const int INF = 2147483647,maxn = 100005;struct node{  int x,y;  bool operator <(const node &a)const{    return x==a.x?y<a.y:x<a.x;  }}a[maxn];node b[maxn];int n,ans,k;inline int solve(int x,int y){  return abs(b[x].x-b[y].x)+abs(b[x].y-b[y].y);}int main(){  //freopen("data","r",stdin);  freopen("troops.in","r",stdin);  freopen("troops.out","w",stdout);  scanf("%d%d",&n,&k);  for(int i=1;i<=n;i++)    scanf("%d%d",&a[i].x,&a[i].y);  sort(a+1,a+n+1);  int Max = a[n].y,tmp = 0,t = 1;  b[++tmp] = a[n];  for(int i=n-1;i;i--)    if(Max<a[i].y)Max = a[i].y,b[++tmp] = a[i];  for(int i=2;i<=tmp;i++){    if(solve(i,i-1)<=k)t++;else ans = max(ans,t),t = 1;   }  ans = max(ans,t);  cout<<ans;  return 0;}

 

  

 

 

noip模拟赛:部队[技巧?思想?]