hiho 1249 Xiongnu's Land - dblank

hiho 1249 Xiongnu's Land

分割线要满足三个条件:

1. 左边的绿洲面积要大于等于右边的绿洲面积。

2.两边的面积的差值要尽可能的小。

3.左边的总面积要尽可能的大于右边。

思路:先二分答案求出条件一和二满足的最左边的分割线,然后二分答案满足条件最右边的分割线。

本来写了一发线段树的,结果写搓了。。。。

#include<iostream>  
#include<set>  
#include<map>  
#include<algorithm>  
#include<cstdio>  
#include<cstring>  
#include<vector>  
#include<queue>  
#include<cmath>  
using namespace std;  
typedef long long ll;  
const int maxn = 1000100;  
int l[maxn], t[maxn], w[maxn], h[maxn], n;  
/*void pushup(int cnt) 
{ 
    sum[cnt] = sum[cnt<<1] + sum[cnt<<1|1]; 
} 
void pushdown(int cnt, int len) 
 
{ 
    if(mark[cnt]) 
    { 
        int m = len / 2; 
        mark[cnt<<1] += mark[cnt]; 
        mark[cnt<<1|1] += mark[cnt]; 
        sum[cnt<<1] += mark[cnt<<1] * (len - m); 
        sum[cnt<<1|1] += mark[cnt<<1|1] * m; 
        mark[cnt] = 0; 
    } 
} 
void update(int nowl, int nowr, int l, int r, int c, int cnt) 
{ 
    if(nowl>=l && nowr<=r) 
    { 
        sum[cnt] += (nowr - nowl + 1)*c; 
        mark[cnt] += c; 
        return ; 
    } 
    pushdown(cnt, nowr - nowl +1); 
    int m = (nowr+nowl)>>1; 
    if(l<=m) 
        update(nowl, m, l, r, c, cnt<<1); 
    if(r>m) 
        update(m+1, nowr, l, r, c, cnt<<1|1); 
    pushup(cnt); 
} 
ll query(int nowl, int nowr, int l, int r, int cnt) 
{ 
    if(nowl>=l && nowr<=r) 
    { 
        return sum[cnt]; 
    } 
    pushdown(cnt, nowr - nowl +1); 
    int m = (nowl+nowr)>>1; 
    ll sum = 0; 
    if(l<=m) 
        sum += query(nowl, m, l, r, cnt<<1); 
    if(r>m) 
        sum += query(m+1, nowr, l, r, cnt<<1|1); 
    pushup(cnt); 
    return sum; 
}*/  
ll get(int x)  
{  
    ll sum = 0;  
    for(int i = 1; i<=n; i++)  
    {  
        sum += (ll)h[i]*(max(min(x-l[i], w[i]), 0));  
    }  
    return sum;  
}  
int main()  
{  
    int T;  
    cin>>T;  
    while(T--)  
    {  
        ll s = 0;  
        int r;  
        scanf("%d", &r);  
        //memset(a, 0, sizeof(a));  
        scanf("%d", &n);  
        //  memset(mark, 0, sizeof(mark));  
        //  memset(sum, 0, sizeof(sum));  
        for(int i = 1; i<=n; i++)  
        {  
            scanf("%d%d%d%d", &l[i], &t[i], &w[i], &h[i]);  
        }  
        s = get(r);  
        int right = r, left = 1, mid;  
        while(left<=right)  
        {  
            mid = (right+left)>>1;  
            ll sum =get(mid);  
            if(sum >= s-sum)  
            {  
                right = mid - 1;  
            }  
            else  
            {  
                left = mid + 1;  
            }  
        }  
         //cout<<left<<endl;  
        ll ans = get(left);  
        right = r, left = 1;  
        //  cout<<ans<<endl;  
        while(left <= right)  
        {  
            mid = (right+left)>>1;  
            ll sum = get(mid);  
            if(sum > ans)  
            {  
                right = mid-1;  
            }  
            else  
            {  
                left = mid+1;  
            }  
        }  
        cout<<right<<endl;  
    }  
    return 0;  
}

 

相关文章

发表新评论