[HOJ 18] 保鏢

作法：

詳細的作法在這個網站已經講的很清楚了，怕這網站會死掉所以備份一下：

-------------------------------------------------

有一个N*M的01矩阵，给出每一行和每一列中1的个数，问是否有可能成立。输入的数据经过压缩，给出n个数对(Ai,Bi)，表示有Bi行有Ai个1；同理给出m个数对(Ci,Di)，表示有Di列有Ci个1（n、m<=2e5，N、M<=1e18）。

    设每行中1的个数是R[i]，每列的是C[i]。我们一开始可以将R[]和C[]从大到小排序，因为它们的先后顺序无关紧要。考虑第一行放得下的必要条件：R[1]<=sigma(min(C[i],1)|1<=i<=M)；同理前k行放得下的必要条件：sigma(i|1<=i<=k)<=sigma(min(C[i],k)|1<=i<=M)。设f(k)=sigma(i|1<=i<=k)，g(k)=sigma(min(C[i],k)|1<=i<=M)，该矩阵成立的必要条件是对于所有1<=k<=N，都有f(k)<=g(k)。可以证明这也是成立的充分条件：

    1.当k=1时正确性显然；

    2.设p=g(k)-g(k-1)=sigma(1|C[i]>=k)表示第k行新增的可以填的格子数，若R[k]<=p，从p个格子中随便找R[k]格填上就行了；

    3.若R[k]>p。因为f(x)=f(x-1)+R[i]<=g(x)=g(x-1)+p且f(x-1)<=g(x-1)，所以g(x-1)-f(x-1)>=R[k]-p，也就是说在上一行中有至少R[k]-p个多余的格子，加上这一行的p个格子，是够满足这一行中R[k]的需求的。

    最后得出结论，本题可以转化为判断f(k)是否恒小于等于g(k)。函数图像y=f(k)和y=g(k)都是折点数在O(n)级别的折线图，可以把这些点全部算出来再加一判断。时间复杂度是排序的O(nlogn+mlogm)。

-------------------------------------------------

比較需要思考的是最後在轉換成折線的部分。如果想像把題目給的全部的數據展開( 例如 3 個 2 就展開成2 2 2 )，然後去算 f 和 g 陣列的值，會發現他其實很大的部分都是直線的，只會有幾個轉折點，而我們知道這些轉折點的位置，例如現在要算 f 陣列，並且題目輸入有 x_i 個 y_i ，那麼就可以知道 f 的轉折點的 x 坐標就是 sigma ( i = 1 ~ k ) x_i 們，因為函數只會在當這一排的數量變動的時候轉折。至於 g 陣列比較不好想，一樣假設這個方向的輸入有 x_i 個 y_i ( 和剛剛不一樣， f 和 g 分別是兩個方向代表的陣列 )，那麼轉折點的 x 坐標就會是 y_k 們，這可以由 g 的定義得出，但需要想一下。

最後要判斷 f 折線是否一直 <= g 折線，而判斷方法是枚舉 f 的轉折點坐標，並且用雙指標知道這個點落在 g 的哪一段折線上，就可以知道在這個轉折點 f 是否 <= g ，並且由函數的形狀可以知道這樣是充要條件。但還要注意的一點是，總不能 f 的轉折點不在 g 的折線的線段上，所以如果 f 的最後一個 x 坐標太右邊的話必須再多加一個 g 的點，他的 x 坐標和 f 的最後一個 x 坐標一樣，而 y 坐標因為 g 在更大都不會變了，所以就會和前一個一樣。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=200000+10 ;
 
struct P
{
    LL x,y ;
    bool operator < (const P &rhs) const
    {
        return x>rhs.x ;
    }
}a[maxn],b[maxn];
 
P f[maxn],g[maxn] ;
 
bool solve(int n,int m)
{
    for(int i=1,j=0;i<=n;i++)
    {
        while(j<m && g[j+1].x<f[i].x) j++ ;
        LL t=(g[j+1].y-g[j].y)/(g[j+1].x-g[j].x) ;
        if(g[j].y + t * (f[i].x-g[j].x) < f[i].y) return 0 ;
    }
    return 1 ;
}
 
main()
{
    int n,m ;
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%I64d%I64d",&a[i].x,&a[i].y) ;
    scanf("%d",&m) ;
    for(int i=1;i<=m;i++) scanf("%I64d%I64d",&b[i].x,&b[i].y) ;
    sort(a+1,a+n+1) ;
    sort(b+1,b+m+1) ;
 
    for(int i=1;i<=n;i++)
        f[i]=(P){f[i-1].x+a[i].y,f[i-1].y+a[i].x*a[i].y} ;
    LL sum=0LL ;
    for(int i=1;i<=m;i++) sum+=b[i].y ;
    for(int i=m;i>=1;i--)
    {
        g[m+1-i].x=b[i].x ;
        g[m+1-i].y=g[m-i].y+(b[i].x-b[i+1].x)*sum ;
        sum-=b[i].y ;
    }
    if(f[n].x > g[m].x) g[m+1]=(P){f[n].x,g[m].y} , m++ ;
    if(solve(n,m)) printf("1\n") ;
    else printf("0\n") ;
}