P3138 [USACO16FEB]负载平衡Load Balancing_Silver

57 阅读 0 评论 38 点赞

我是靠谱客的博主潇洒咖啡豆，最近开发中收集的这篇文章主要介绍P3138 [USACO16FEB]负载平衡Load Balancing_Silver，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://www.luogu.org/problemnew/show/P3138

题目描述

农民约翰的N只牛分别站在他的二维农场的不同位置（x1,y1）…(xn,yn)（1<=N<=100000,xi和yi是正整奇数）。他想建一排无限长度的南北方向的满足等式x=a的围栏来把他的农场分成两部分（a是一个偶数，确保了不会使围栏建在任何一只牛的位置上）。他也想建一个无限长度的东西方向的满足等式y=b的围栏（b也是偶数）。这两个围栏在（a,b）点相交，并把农场分成了四个区域。约翰想选一对a和b使四个区域是"平衡"的，即不要让一个区域包含太多的牛。令M为四个区域中牛的数量的最大值，约翰想使M尽量的小。请帮他求出最小的M。输入格式

第一行包含两个整数N和B。接下来的N行每行包含一只牛的位置x和y。

输出格式

输出M的最小值

输入样例

7

7 3

5 5

9 7

3 1

7 7

5 3

9 1

输出样例

2

　1.首先离散y坐标，然后处理处关于横坐标的前缀和，表示当前在位置的y划分的结果。

　2.然后模拟扫描线沿着行方向自上向下扫描，相当于枚举x轴的划分。

　3.对于每一种x轴的划分，可以发现 : 令f（y）表示在当前位置划分的函数值是单峰的，所以就可以套三分了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,pos[100050],sum[100050],now;
 4 int c[100050],ans,l,r,tl,tr,tot;
 5 struct node
 6 {
 7     int x,y,tmp;
 8     bool operator<(const node & p)const
 9     {
10         return x==p.x? tmp<p.tmp:x<p.x;
11     }
12 }num[100050];
13 bool cmp(int a,int b)
14 {
15     return num[a].tmp<num[b].tmp;
16 }
17 void calc_push(int u)
18 {
19     while(u<=now)
20     {
21         ++c[u];
22         u+=u&-u;
23     }
24 }
25 int calc_ask(int u)
26 {
27     int cnt=0;
28     while(u)
29     {
30         cnt+=c[u];
31         u-=u&-u;
32     }
33     return cnt;
34 }
35 int check(int u)
36 {
37     int tmp=calc_ask(u);
38     int ent=max(max(tmp,tot-1-tmp),max(sum[u]-tmp,n-(sum[u]-tmp+tot-1)));
39     ans=min(ans,ent);
40     return ent;
41 }
42 void calc()
43 {
44     l=1,r=now;
45     while(l<r)
46     {
47         tl=((l<<1)+r)/3;
48         tr=(l+(r<<1))/3;
49         if(l==tl)    ++tl;
50         if(r==tr)     --tr;
51         if(check(tl)<check(tr))     r=tr;
52         else     l=tl;
53     }
54 }
55 int main()
56 {
57     scanf("%d",&n);ans=n;
58     for(int i=1;i<=n;++i)
59     {
60         scanf("%d%d",&num[i].x,&num[i].tmp);
61         pos[i]=i;
62     }
63     sort(num+1,num+n+1);
64     sort(pos+1,pos+n+1,cmp);
65     for(int i=1;i<=n;++i)
66     {
67         if(num[pos[i]].tmp!=num[pos[i-1]].tmp)
68         {
69             ans=min(ans,max(sum[now],n-sum[now]));
70             sum[now+1]=sum[now];
71             ++now;
72         }
73         num[pos[i]].y=now;
74         ++sum[now];
75     }
76     for(int i=1;i<=n;i=tot)
77     {
78         tot=i;
79         while(num[tot].x==num[i].x)
80             calc_push(num[tot++].y);
81         calc();
82     }
83     printf("%d",ans);
84     return 0;
85 }