BZOJ 1805: [IOI2007]Sails – [线段树/贪心]


题目传送门(BZOJ)

题解 :

温馨提示, 光标悬停在公式上可以放大

首先 : 定义单个旗杆为一列, 能互相产生推动力折扣的为一行
证明如下三个性质(希望直接看到解题步骤请跳过这部分) :

性质 1 : 旗杆顺序和答案无关

我们发现每行所能产生的推动力损耗只和这行帆的数量有关
若第 i 行所具有的帆数量为 F[i],
那么这行产生的答案贡献是 \frac{F[i]\times (F[i]-1)}{2}
总的答案就是 \sum\limits_{i=1}^{maxHeight}\frac{F[i]\times (F[i]-1)}{2}
这个性质的证明是从推动力损耗的定义中得来的

性质 2 : 需要在某旗杆上放一面旗时, 放在当前所有行中帆数量最少的那一行一定不会比其他行差

命题 : 由于帆越多, 损耗越大, 若存在某行 i 帆数为 x, 另一行 j 帆数 \le x-2,
且能从第 i 行把一面帆移动到第 j 行时, 移动之一定会使答案更优

证明 : 令第 i 行帆数量为 x, 第 j 行数量为 y, 且 y \le x-2
那么 原答案为 \frac{x\times (x-1)+y\times (y-1)}{2} \cdots \qquad \qquad(1)
挪动一面帆的答案为 \frac{(x-1)\times(x-2)+(y+1)\times y}{2} \cdots \qquad (2)
只需证明 (2)<(1) 即可
那么 (2)\times 2 – (1)\times 2
2y-2x+3<0
y \le x-2 可得, 2y-2x+4 \le 0, 故命题得证

故只要证明现在放和未来放等价或者不会更劣即可,
发现现在不选最小的, 未来在保证答案最优的情况下也一定会选最小的
由于每行对答案的贡献只和帆数有关, 所以现在放和未来放等价, 且未来必然会放这行, 故现在放在该行即可

性质 3 :

令每行的帆数量为 F[i], 那么设最下面一行为起始行 1, F[]必然是一个单调不增的序列
首先我们知道可以放帆的数量一定是一个单调不增的序列
那么假设有行i > j, 且 F[i] > F[j],
由于 ij 多出来那部分的旗杆一定还没有放帆 (不然就不是多出来的了)
故第 i 行的该面帆必然可以放在第 j 行, 使得 F[i], F[j] 的大小交换, 且对答案无影响


本题需要用到的性质证明完毕

由于性质(1), 我们可以从大到小把所有旗杆排个序, 不会对答案产生影响.
题目就变成了对于每个旗杆 i, 从最小且高度小于 h[i] 的所有行中选出最小的(由性质(2)) k[i] 行, 并在这些行上多放一面旗
由于性质(3), 这 k[i] 行一定是从 h[i] 开始向下共 k[i]
看上去我们直接找到 L = h[i]-k[i]+1 这个点, 然后把 L \sim h[i] 这部分区间加 1 即可
但是发现当区间加 1 之后, 不一定能保证性质(3),
这种情况当且仅当 $F[L] F[L-1]时才会发生.
不过这不是什么重要的问题, 设
x = F[L], 那么在L \sim h[i]F[i] < x的行已经可以加1
设这部分加
1的长度为Len, 我们只要再补k[i]-Len个加1即可
而帆数量恰好等于
x的行数一定大于这个k[i]-Len(从L到刚刚加的起始点, 恰好是k[i]-Lenx)
我们直接在所有值恰好等于
x的行中, 挑选最下面的k[i]-Len行即可,
这样就在保证选了最小的
k[i]$ 个的情况下, 又满足了性质(3)
按这个规则把所有旗杆都做完之后, 直接统计一下每行都有多少, 计算答案即可

线段树需要维护区间最大/最小值, 支持区间修改, 支持查询权值为 x 的最左/最右端点, 支持查询某点 x 的权值
复杂度 O(N\log N)

代码 :

#include 
#include 
#include 
#include 
#define ls p << 1
#define rs p << 1|1
using namespace std;
const int N = 100100;
char buf[100000], *p1, *p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
inline int read() {
    int x = 0; char ch = nc();
    while(ch < 48) ch = nc();
    while(ch > 47) x = (x<<3)+(x<<1)+(ch^48), ch = nc();
    return x;
}
struct MAST {
    int h, k;
    bool operator < (const MAST &A) const {
        return h < A.h;
    }
}a[N];
struct SEGTREE {
    int mn[N<<2], mx[N<<2], laz[N<<2];
    inline void pushUp(int p) {
        mn[p] = min(mn[ls], mn[rs]);
        mx[p] = max(mx[ls], mx[rs]);
    }
    inline void giv(int p, int c) {
        mn[p] += c;
        mx[p] += c;
        laz[p] += c;
    }
    inline void pushDown(int p) {
        if(laz[p]) {
            giv(ls, laz[p]);
            giv(rs, laz[p]);
            laz[p] = 0;
        }
    }
    int getKth(int l, int r, int p, int K) {
        if(l == r) return mn[p];
        pushDown(p);
        int mid = (l+r) >> 1;
        if(K <= mid) return getKth(l, mid, ls, K);
        else return getKth(mid+1, r, rs, K);
    }
    int getLeft(int l, int r, int p, int x) {
        if(l == r) return l;
        pushDown(p);
        int mid = (l+r) >> 1;
        if(mn[ls] <= x) return getLeft(l, mid, ls, x);
        else return getLeft(mid+1, r, rs, x);
    }
    int getRight(int l, int r, int p, int x) {
        if(l == r) return l;
        pushDown(p);
        int mid = (l+r) >> 1;
        if(mx[rs] < x) return getRight(l, mid, ls, x);
        else return getRight(mid+1, r, rs, x);
    }
    void change(int l, int r, int p, int x, int y) {
        if(x <= l && y >= r) return giv(p, 1);
        pushDown(p);
        int mid = (l+r) >> 1;
        if(x <= mid) change(l, mid, ls, x, y);
        if(y >  mid) change(mid+1, r, rs, x, y);
        pushUp(p);
    }
    long long getAns(int l, int r, int p) {
        if(l == r) return (long long)mn[p]*(mn[p]-1)/2;
        pushDown(p);
        int mid = (l+r) >> 1;
        return getAns(l, mid, ls)+getAns(mid+1, r, rs);
    }
}Tr;
long long ans;
int n, maxHeight;
int main() {
    n = read();
    for(int i = 1; i <= n; i ++ ) a[i].h = read(), a[i].k = read(), maxHeight = max(maxHeight, a[i].h);
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; i ++ ) {
        int K = Tr.getKth(1, maxHeight, 1, a[i].h-a[i].k+1);
        int L = Tr.getLeft(1, maxHeight, 1, K);
        int R = Tr.getRight(1, maxHeight, 1, K);
        if(R < a[i].h) {
            Tr.change(1, maxHeight, 1, R+1, a[i].h);
            Tr.change(1, maxHeight, 1, L, L+(a[i].k-a[i].h+R)-1);
        }
        else {
            Tr.change(1, maxHeight, 1, L, L+a[i].k-1);
        }
    }
    ans = Tr.getAns(1, maxHeight, 1);
    printf("%lld\n", ans);
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注