首页 > 代码库 > 【枚举+优化】10396 - 组队
【枚举+优化】10396 - 组队
【枚举+优化】10396 - 组队
Time Limit: 1000MS
Memory Limit: 65536KB
NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为minV,身高最矮的球员高度为minH,那么这支球队的所有队员都应该满足:
A * ( height – minH ) + B * ( speed – minV ) <= C
其中A和B,C为给定的经验值。这个式子很容易理解,如果一个球队的球员速度和身高差距太大,会造成配合的不协调。
请问作为球队管理层的你,在N名选秀球员中,最多能有多少名符合条件的候选球员。
输入
第一行四个数N、A、B、C
下接N行每行两个数描述一个球员的height和speed
输出
最多候选球员数目。
样例
输入:
4 1 2 10
5 1
3 2
2 3
2 1
输出:
4
数据范围:
N <= 5000 ,height和speed不大于10000。A、B、C在长整型以内。
这题我开始一直SB
连最朴素的三重循环都写不来
我开始一直想先枚举人的个数
TMD我后来才知道枚举的时候就可以直接判断
这就是基础不好的后果 哎=。=
思路:
A * ( height – minH ) + B * ( speed – minV ) <= C
可以变形为
A * height + B * speed <= C + A * minH + B * minV
而每次枚举minH minV 是确定了的
将(A * height + B * speed)排个序
所以容易知道if(A * height + B * speed>C + A *minH + B * minV)
所以后面的都可以不用枚举了
Source
四川省NOI2007省集训队选拔
O(n3)30分
1 # include<cstdio> 2 # include<cstring> 3 # include<iostream> 4 # include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int maxn=5000+10; 8 LL N,A,B,C,tot,t; 9 LL height[maxn],speed[maxn];10 int main(){11 t=-1;12 ios::sync_with_stdio(false);13 cin>>N>>A>>B>>C;14 for(int i=1;i<=N;i++)15 cin>>height[i]>>speed[i];16 17 for(int i=1;i<=N;i++)18 for(int j=1;j<=N;j++){19 tot=0;20 for(int k=1;k<=N;k++)21 if(height[k]>=height[i]&&speed[k]>=speed[j]&&A*(height[k]-height[i])+B*(speed[k]-speed[j])<=C)22 tot++;23 t=max(t,tot);24 }25 cout<<t;26 return 0;27 }
【枚举+优化】10396 - 组队