首页 > 代码库 > [ An Ac a Day ^_^ ] HihoCoder 1249 Xiongnu's Land 线性扫描
[ An Ac a Day ^_^ ] HihoCoder 1249 Xiongnu's Land 线性扫描
拿到了icpc北京站的参赛名额 感谢亮哥~
虽然是地狱之战 但也要全力以赴！
题意：
有一片沙漠 n片绿洲 让你用一条线分成两部分
左≥右 而且分割线要尽量靠右 问线的位置
思路：
网上说可以二分 没太看懂……
还有一种思路就是线性扫描
将二维的图化成一维的线 然后从头扫一遍
遇到左≥sum/2时试探着向右继续扫
最后输出答案
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<math.h> 5 #include<string.h> 6 #include<string> 7 #include<map> 8 #include<set> 9 #include<vector>10 #include<queue>11 #define M(a,b) memset(a,b,sizeof(a))12 using namespace std;13 typedef long long ll;14 const int inf=0x3f3f3f;15 const int maxn=1e6+10;16 ll line[maxn];17 int main(){18 int T;19 scanf("%d",&T);20 while(T--){21 int sq;22 scanf("%d",&sq);23 int n;24 scanf("%d",&n);25 int x,y,w,h;26 M(line,0);27 ll sum=0;28 for(int i=0;i<n;i++){29 scanf("%d%d%d%d",&x,&y,&w,&h);30 for(int j=x;j<x+w;j++){ //将二维的图转化成一维的线 使时间复杂度达到线性时间O(n)31 line[j]+=h;32 sum+=h;33 }34 }35 sum++;36 sum/=2;37 ll cal=0;38 for(int i=0;i<=sq;i++){ //扫描39 cal+=line[i];40 if(cal>=sum){ //已经符合题意41 i++;42 while(line[i]==0&&i<sq) i++; //试探着继续扫43 printf("%d\n",i);44 break;45 }46 }47 }48 return 0;49 }50 /*51 52 253 100054 255 1 1 2 156 5 1 2 157 100058 159 1 1 2 160 61 */
[ An Ac a Day ^_^ ] HihoCoder 1249 Xiongnu's Land 线性扫描
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。