拿到了icpc北京站的参赛名额 感谢亮哥~
虽然是地狱之战 但也要全力以赴！
题意：
有一片沙漠 n片绿洲 让你用一条线分成两部分
左≥右 而且分割线要尽量靠右 问线的位置
思路：
网上说可以二分 没太看懂……
还有一种思路就是线性扫描
将二维的图化成一维的线 然后从头扫一遍
遇到左≥sum/2时试探着向右继续扫
最后输出答案
不知道为啥hihocoder能过uvalive死活就是过不去……
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f;
const int maxn=1e6+;
ll line[maxn];
int main(){
int T;
scanf("%d",&T);
while(T--){
int sq;
scanf("%d",&sq);
int n;
scanf("%d",&n);
int x,y,w,h;
M(line,);
ll sum=;
for(int i=;i<n;i++){
scanf("%d%d%d%d",&x,&y,&w,&h);
for(int j=x;j<x+w;j++){ //将二维的图转化成一维的线 使时间复杂度达到线性时间O(n)
line[j]+=h;
sum+=h;
}
}
sum++;
sum/=;
ll cal=;
for(int i=;i<=sq;i++){ //扫描
cal+=line[i];
if(cal>=sum){ //已经符合题意
i++;
while(line[i]==&&i<sq) i++; //试探着继续扫
printf("%d\n",i);
break;
}
}
}
return ;
}
/* 2
1000
2
1 1 2 1
5 1 2 1
1000
1
1 1 2 1 */