网站后缀名,郴州网红,公司注册代理注册,网站建设数字的代码编写https://www.luogu.org/problemnew/show/P3138 题目描述 农民约翰的N只牛分别站在他的二维农场的不同位置#xff08;x1,y1#xff09;…(xn,yn)#xff08;1N100000,xi和yi是正整奇数#xff09;。他想建一排无限长度的南北方向的满足等式xa的围栏来把他的农场分成… https://www.luogu.org/problemnew/show/P3138 题目描述 农民约翰的N只牛分别站在他的二维农场的不同位置x1,y1…(xn,yn)1N100000,xi和yi是正整奇数。他想建一排无限长度的南北方向的满足等式xa的围栏来把他的农场分成两部分a是一个偶数确保了不会使围栏建在任何一只牛的位置上。他也想建一个无限长度的东西方向的满足等式yb的围栏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轴的划分可以发现 : 令fy表示在当前位置划分的函数值是单峰的所以就可以套三分了。 1 #includebits/stdc.h2 using namespace std;3 int n,m,pos[100050],sum[100050],now;4 int c[100050],ans,l,r,tl,tr,tot;5 struct node6 {7 int x,y,tmp;8 bool operator(const node p)const9 {
10 return xp.x? tmpp.tmp:xp.x;
11 }
12 }num[100050];
13 bool cmp(int a,int b)
14 {
15 return num[a].tmpnum[b].tmp;
16 }
17 void calc_push(int u)
18 {
19 while(unow)
20 {
21 c[u];
22 uu-u;
23 }
24 }
25 int calc_ask(int u)
26 {
27 int cnt0;
28 while(u)
29 {
30 cntc[u];
31 u-u-u;
32 }
33 return cnt;
34 }
35 int check(int u)
36 {
37 int tmpcalc_ask(u);
38 int entmax(max(tmp,tot-1-tmp),max(sum[u]-tmp,n-(sum[u]-tmptot-1)));
39 ansmin(ans,ent);
40 return ent;
41 }
42 void calc()
43 {
44 l1,rnow;
45 while(lr)
46 {
47 tl((l1)r)/3;
48 tr(l(r1))/3;
49 if(ltl) tl;
50 if(rtr) --tr;
51 if(check(tl)check(tr)) rtr;
52 else ltl;
53 }
54 }
55 int main()
56 {
57 scanf(%d,n);ansn;
58 for(int i1;in;i)
59 {
60 scanf(%d%d,num[i].x,num[i].tmp);
61 pos[i]i;
62 }
63 sort(num1,numn1);
64 sort(pos1,posn1,cmp);
65 for(int i1;in;i)
66 {
67 if(num[pos[i]].tmp!num[pos[i-1]].tmp)
68 {
69 ansmin(ans,max(sum[now],n-sum[now]));
70 sum[now1]sum[now];
71 now;
72 }
73 num[pos[i]].ynow;
74 sum[now];
75 }
76 for(int i1;in;itot)
77 {
78 toti;
79 while(num[tot].xnum[i].x)
80 calc_push(num[tot].y);
81 calc();
82 }
83 printf(%d,ans);
84 return 0;
85 } 代码 转载于:https://www.cnblogs.com/wyher/p/9800034.html
