平衡 balance
2018-09-18 06:25:07来源:博客园 阅读 ()
题面
草地上有 N 头牛,坐标分别为(x1,y1)…(xn,yn),(1≤N≤1000,坐标值都是正的奇数,其不超过 1,000,000)。
现在需要划一条 x 轴和一条 y 轴,值为正的偶数,将草地分成四个区域。为了平衡,现在希望每个区域上牛的数量尽量平均。对于某个划分方案,设M 为四个区域中牛的数量的最大值。
求一种划分方案,使得 M 值最小。
【输入文件】
第 1 行 1 个整数 N;
接下来 N 行,每行两个正奇数,表示一头牛的坐标。
【输出文件】
共 1 行 1 个整数,表示 M 的最小值。
7 7 3 5 5 7 13 3 11 1 7 5 3 9 1
2
样例图片
思路
对于样例,我们可知其实对于牛的划分,每个牛的位置并不重要,我们只需要知道相对位置就可以进行划分。
所以对于每个点离散化它的坐标,使其呈现出x第几大,y第几大的结构。
再用前缀和模拟求解即可。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{int x,y,numx,numy;}a[1005]; 4 int n,maxn=1,maxm=1,minn=999999,b[1005][1005],sum[1005][1005]; 5 inline bool cmp1(node a,node b){return a.x<b.x;} 6 inline bool cmp2(node a,node b){return a.y<b.y;} 7 int main(){ 8 cin>>n; 9 for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y; 10 sort(a+1,a+n+1,cmp1); 11 a[1].numx=1; 12 for (int i=2;i<=n;i++) if (a[i].numx==a[i-1].numx) a[i].numx=a[i-1].numx;else a[i].numx=a[i-1].numx+1,maxn++; 13 sort(a+1,a+n+1,cmp2); 14 a[1].numy=1; 15 for (int i=2;i<=n;i++) if (a[i].numy==a[i-1].numy) a[i].numy=a[i-1].numy;else a[i].numy=a[i-1].numy+1,maxm++; 16 for (int i=1;i<=n;i++) b[a[i].numx][a[i].numy]=1; 17 for(int i=1;i<=maxn;i++) for(int j=1;j<=maxm;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+b[i][j]; 18 for(int i=1;i<=maxn;i++)for(int j=1;j<=maxm;j++) minn=min(minn,max(max(sum[i][j],sum[i][maxm]-sum[i][j]),max(sum[maxn][j]-sum[i][j],sum[maxn][maxm]-sum[i][maxm]-sum[maxn][j]+sum[i][j]))); 19 cout<<minn<<endl; 20 return 0; 21 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 二叉树(五)平衡二叉树(AVL树) 2020-02-05
- 「BZOJ4173」数学 2020-01-15
- 平衡树学习笔记 2019-11-28
- 【CSP-S膜你考】 A 2019-10-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash