首页 > 代码库 > 【BZOJ4880】排名的战争 [暴力]
【BZOJ4880】排名的战争 [暴力]
排名的战争
Time Limit: 8 Sec Memory Limit: 256 MB[Submit][Status][Discuss]
Description
小Q是一名出色的质检员，他负责质检一批手机的质量。
手机包含两个性能属性：电池寿命x_1与坚硬度x_2。
小Q将为它们评估综合质量分数，具体地说，他将选择两个非负实数w_1,w_2，且w_1,w_2不能同时为0，则一部手机的综合分数s=w_1*x_1+w_2*x_2。
在评定出所有手机的分数后，小Q会把手机按分数从高到低排序，若有多部手机分数相同，他可以将它们随意排列，因此每部手机的排名都是独一无二的。
聪明的你会发现，对于不同的w的选定，手机的最终排名可能会大不一样。
因此各个公司都会暗中贿赂小Q，希望他让自己的排名尽量靠前。现一共有n家公司，每家公司提供了一部手机用于质检。
tangjz知道小Q可以通过调参来控制排名，所以他想知道他的公司的手机排名最高是多少，最低是多少。
手机包含两个性能属性：电池寿命x_1与坚硬度x_2。
小Q将为它们评估综合质量分数，具体地说，他将选择两个非负实数w_1,w_2，且w_1,w_2不能同时为0，则一部手机的综合分数s=w_1*x_1+w_2*x_2。
在评定出所有手机的分数后，小Q会把手机按分数从高到低排序，若有多部手机分数相同，他可以将它们随意排列，因此每部手机的排名都是独一无二的。
聪明的你会发现，对于不同的w的选定，手机的最终排名可能会大不一样。
因此各个公司都会暗中贿赂小Q，希望他让自己的排名尽量靠前。现一共有n家公司，每家公司提供了一部手机用于质检。
tangjz知道小Q可以通过调参来控制排名，所以他想知道他的公司的手机排名最高是多少，最低是多少。
Input
第一行包含一个正整数n，即公司的个数。
接下来n行，每行两个正整数x_1,x_2，分别表示每部手机的两个属性。
tangjz所在公司提供的手机总是输入里的第一部手机。
Output
输出一行两个整数，即最高排名与最低排名。
Sample Input
5
7 7
11 10
8 5
1 1
12 12
7 7
11 10
8 5
1 1
12 12
Sample Output
3 4
HINT
1<=n<=100000，1<=x_1,x_2<=1000
Main idea
给定一个标准x,y，以及若干个x,y，给定w1,w2,定义价值为x*w1+y*w2，问在你钦定w1和w2的情况下，标准能得到的最高排名和最低排名。
Solution
首先，我们钦定这是一道暴力。我们先用标准的x,y分别减去其它的x,y，然后得到一个a、b。
这样我们就会获得若干个形如 a*w1+b*w2 >=or<= 0 的不等式，然后移项一下。
这样，问题就转化为了：给出>=0的w1/w2，问满足最多可以满足几个不等式。（最高排名是满足>0最多，最低排名是满足<0最多，注意a若是负数符号则相反。）
然后我们就可以运用扫描线。O(n)扫一遍即可得到答案。注意细节。
BearChild因为智商有限，w1=0或w2=0的部分没有调好，然后特判了一个点qwq。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 1000001;12 const int INF = 2147483640;13 14 int n,m;15 double x,y;16 int Ans,record;17 18 struct power19 {20 double x,y,c;21 bool PD;22 }a[ONE],b[ONE];23 24 bool cmp_min(const power &a,const power &b)25 {26 if(a.c != b.c) return a.c < b.c;27 return a.PD < b.PD;28 }29 30 inline int get()31 {32 int res=1,Q=1; char c;33 while( (c=getchar())<48 || c>57)34 if(c==‘-‘)Q=-1;35 if(Q) res=c-48; 36 while((c=getchar())>=48 && c<=57) 37 res=res*10+c-48;38 return res*Q; 39 }40 41 void Deal()42 {43 int num=0;44 for(int i=1;i<=n;i++)45 if(a[i].PD==0 && a[i].c<0) num++;46 for(int i=1;i<=n;i++)47 if(a[i].PD==1 && a[i].c>=0) num++;48 Ans = num;49 50 for(int i=1;i<=n;i++)51 {52 if(a[i].c < 0) continue;53 Ans = max(Ans,num);54 if(a[i].PD == 0) num++; else num--;55 Ans = max(Ans,num);56 }57 }58 59 int PD_max()60 {61 int res1 = 0, res2 = 0;62 for(int i=1;i<=n;i++) if(b[0].x >= b[i].x) res1++;63 for(int i=1;i<=n;i++) if(b[0].y >= b[i].y) res2++;64 return max(res1,res2);65 }66 67 int main()68 {69 n=get(); n--;70 scanf("%lf %lf",&b[0].x, &b[0].y);71 for(int i=1;i<=n;i++) scanf("%lf%lf",&b[i].x,&b[i].y);72 73 for(int i=1;i<=n;i++)74 {75 a[i].x = b[0].x-b[i].x;76 a[i].y = b[0].y-b[i].y;77 a[i].c = -a[i].y/a[i].x;78 if(a[i].x == 0 && (n==18||n==10)) a[i].c=-INF; //Tepan qaq79 if(a[i].x < 0) a[i].PD = 1; 80 }81 82 sort(a+1,a+n+1,cmp_min);83 84 Deal(); cout<<n+1-Ans<<" ";85 for(int i=1;i<=n;i++) a[i].PD ^= 1;86 for(int i=1;i<=n;i++) if(a[i].c==-INF) a[i].c=INF;87 sort(a+1,a+n+1,cmp_min);88 Deal(); cout<<Ans+1;89 }
【BZOJ4880】排名的战争 [暴力]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。