UVALive-7261: Xiongnu's Land（前缀和）

杂

Description

Wei Qing (died 106 BC) was a military general of the Western Han dynasty whose campaigns against the Xiongnu earned him great acclaim. He was a relative of Emperor Wu because he was the younger half-brother of Empress Wei Zifu (Emperor Wu’s wife) and the husband of Princess Pingyang. He was also the uncle of Huo Qubing, another notable Han general who participated in the campaigns against the Xiongnu and exhibited outstanding military talent even as a teenager.

Defeated by Wei Qing and Huo Qubing, the Xiongnu sang: “Losing my Qilian Mountains, made my cattle unthriving; Losing my Yanzhi Mountains, made my women lacking rouge.”
The text above is digested from Wikipedia. Since Wei and Huo’s distinguished achievements, Emperor Wu decided to give them some awards — a piece of land taken by them from Xiongnu. This piece of land was located in a desert, and there were many oases in it. Emperor Wu wanted to draw a straight south-to-north dividing line to divide the land into two parts, and gave the western part to Wei Qing while gave the eastern part to Huo Qubing. There are two rules about the land dividing:

1. The total area of the oases lay in Wei’s land must be larger or equal to the total area of the oases
   lay in Huo’s land, and the difference must be as small as possible.

2. Emperor Wu wanted Wei’s land to be as large as possible without violating the rule 1.

To simplify the problem, please consider the piece of land given to Wei and Huo as a square on a plane. The coordinate of its left bottom corner was (0, 0) and the coordinate of its right top corner was (R, R). Each oasis in this land could also be considered as a rectangle which was parallel to the coordinate axes. The equation of the dividing line was like x = n, and n must be an integer. If the dividing line split an oasis, then Wei owned the western part and Huo owned the eastern part. Please help Emperor Wu to find out how to draw the dividing line.

Input

The first line of the input is an integer K meaning that there are K (1 ≤ K ≤ 15) test cases.
For each test case:
The first line is an integer R, indicating that the land’s right top corner was at (R, R) (1 ≤ R ≤ 1, 000, 000)
Then a line containing an integer N follows, indicating that there were N (0 < N ≤ 10000) oases.
Then N lines follow, each contains four integers L, T, W and H, meaning that there was an oasis whose coordinate of the left top corner was (L, T), and its width was W and height was H. (0 ≤ L, T ≤ R, 0 < W, H ≤ R). No oasis overlaps.

Output

For each test case, print an integer n, meaning that Emperor Wu should draw a dividing line whose equation is x = n. Please note that, in order to satisfy the rules, Emperor might let Wei get the whole land by drawing a line of x = R if he had to.

Sample Input

2
1000
2
1 1 2 1
5 1 2 1
1000
1
1 1 2 1

Sample Output

5
2

题意：输入t，有t组数据，每组输入r（一个正方形的沙漠的边长），n（沙漠里有多少绿洲），接下来n行，每行输入4个数字，$l,t,w,h，（l,t）$是绿洲的左上角的位置，w是它的长，h是宽。然后需要我们用一条从上到下的直线，把这个沙漠分成两部分，要使左右两边的绿洲面积相差最小，并且是左边绿洲面积$≥$右边绿洲面积，在绿洲面积相差最小的情况下，还要尽可能使左边的总面积大于右边的总面积。输出分割这两部分的这条直线$x=？$。【这个题建坐标系和我们数学建系一样，左下角是原点，好像没有影响】

分析：输入一个绿洲的信息，我们知道它的x坐标，从这个x坐标开始到它的最右端，每一段的高度都是h，那么用一个数组x来将长度装进去，即x[j]+=a[i].h，那么其实就得到每一列拥有绿洲的面积是多少（也可以用前缀和做）。再从左向右依次加起来，大于总绿洲面积的一半之后就break。再向右边找，如果右边绿洲面积为0，那么还可以向右走，直到右边绿洲面积不为0。

看图，大概是这个意思= =

• 完整代码：

#include<stdio.h>
#include<string.h>
#define LL long long
struct node 
{
    LL l,t,w,h;
}a[10005];
LL x[1000005];
int main()
{
    LL t,r,n,area,s,ans;
    scanf("%lld",&t);
    while(t--)
    {
        area=0,s=0;
        memset(x,0,sizeof(x));
        scanf("%lld%lld",&r,&n);
        for(LL i=1;i<=n;i++)
        {
            scanf("%lld%lld%lld%lld",&a[i].l,&a[i].t,&a[i].w,&a[i].h);
            area+=a[i].w*a[i].h;
            for(LL j=a[i].l+1;j<=a[i].l+a[i].w;j++) 
            //只经过一条线是没有面积的，要扫到下一条线上才会有面积，所以是a[i].l+1
                x[j]+=a[i].h;
        }
        area=(area+1)/2;
        LL k;
        for(LL i=1;i<=r;i++)
        {
            s+=x[i];
            if(s>=area)
            {
                k=i;
                break;
            }
        }
        ans=k;
        for(LL i=k+1;i<=r;i++) //看右边那一列是不是有绿洲的
        {
            if(x[i]==0)
                ans=i;
            else
                break;
        }
        printf("%lld\n",ans);
    }
    return 0;
}