首页 > 代码库 > BZOJ 4880

BZOJ 4880

2024-09-22 08:34:45   218人阅读

      这道题我们这样考虑，对于1号手机的两个属性X1和Y1，和其他手机的两个属性X2和Y2，如果有W1*X1+W2*Y1>=W1*X2+W2*Y2，那么1号手机就优于2号手机，这样我们进行移项，可以根据X1和X2的大小关系讨论出两种情况：(Y2-Y1)/(X1-X2)<=W1/W2 ，(Y2-Y1)/(X1-X2)>=W1/W2 。对于X1=X2的情况，我们是可以讨论出谁更优的，这样我们就发现问题转化成了在一些斜率中确定一个斜率，使得满足上述条件的数目最多或最少，我们可以证明最优的斜率一定是这些斜率中的一个，这样我们就可以对斜率排序，然后枚举一下，就可以计算了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define maxn 100005
 6 struct Vergil
 7 {
 8     int x,y;
 9     bool operator < (const Vergil &a) const 
10     {
11         bool pd=((x<0)^(a.x<0));
12         return pd?y*a.x>x*a.y:y*a.x<x*a.y;
13     }
14 }k1[maxn],k2[maxn];
15 int n,X,Y,tot1,tot2,L1,L2,ans1,ans2,cur1[2],cur2[2];
16 
17 inline int read(void)
18 {
19     int x=0;
20     char ch=getchar();
21     while (ch>‘9‘||ch<‘0‘) ch=getchar();
22     while (ch>=‘0‘&&ch<=‘9‘)
23     {
24         x=x*10+ch-‘0‘;
25         ch=getchar();
26     }
27     return x;
28 }
29 
30 int main()
31 {
32     n=read()-1;X=read();Y=read();
33     for (int i=1;i<=n;i++) 
34     {
35         int x=read(),y=read();
36         if (x<X) k1[++tot1]=(Vergil){X-x,y-Y};
37         if (x>X) k2[++tot2]=(Vergil){X-x,y-Y};
38         if (x==X)
39         {
40             if (y<Y) L1++,L2++;
41             if (y==Y) L1++;
42         }
43         cur1[0]+= x<=X;
44         cur1[1]+= x<X;
45         cur2[0]+= y<=Y;
46         cur2[1]+= y<Y;
47     }
48     sort(k1+1,k1+tot1+1);
49     sort(k2+1,k2+tot2+1);
50     ans1=0;ans2=n+4;
51     for (int i=1;i<=tot1;i++) 
52     {
53         if (k1[i].x*k1[i].y<0) continue;
54         int a=i-1,b=i;
55         int p1=lower_bound(k2+1,k2+tot2+1,k1[i])-k2;
56         int p2=upper_bound(k2+1,k2+tot2+1,k1[i])-k2;
57         a+=(tot2-p2+1);b+=(tot2-p1+1);
58         ans1=max(ans1,b);
59         ans2=min(ans2,a);
60     }
61     for (int i=1;i<=tot2;i++) 
62     {
63         if (k2[i].x*k2[i].y<0) continue;
64         int a=tot2-i,b=tot2-i+1;
65         int p1=lower_bound(k1+1,k1+tot1+1,k2[i])-k1;
66         int p2=upper_bound(k1+1,k1+tot1+1,k2[i])-k1;
67         a+=(p1-1);b+=(p2-1);
68         ans1=max(ans1,b);
69         ans2=min(ans2,a);
70     }
71     ans1+=L1;ans2+=L2;
72     ans1=max(ans1,max(cur1[0],cur2[0]));
73     ans2=min(ans2,min(cur1[1],cur2[1]));
74     printf("%d %d\n",n+1-ans1,n+1-ans2);
75     return 0;
76 }

 

BZOJ 4880


联系
我们