2019牛客暑期多校训练营 (第七场) - C - Governing sand

2019-08-12 ACM 阅读量

The Wow village is often hit by wind and sand,the sandstorm seriously hindered the economic development of the Wow village.
There is a forest in front of the Wowo village, this forest can prevent the invasion of wind and sand. But there is a rule that the number of tallest trees in the forest should be more than half of all trees, so that it can prevent the invasion of wind and sand. Cutting down a tree need to cost a certain amount of money. Different kinds of trees cost different amounts of money. Wow village is also poor.There are n kinds of trees. The number of i-th kind of trees is $P_i$ , the height of i-th kind of trees is $H_i$，the cost of cutting down one i-th kind of trees is $C_i$.

题意

$N$ 种树，每种树有一个高度，砍掉需要的花费，以及数量。现在我们要把最高的树的数目严格大于所有树数目的一半。问所需要的最小花费是多少。

题目链接

Governing sand

输入输出格式

输入格式

多组输入输出且不超过30组
对于每组测试样例
第一行一个 $N$ 表示有 $N$ 种树 $ 1 \leq N \leq 10^5 $。
剩下 $N$ 行，每行有三个数 $H_i$ ($ 1 \leq H_i \leq 10^9 $)， $C_i$ ($ 1 \leq C_i \leq 200 $)，$P_i$ ($ 1 \leq P_i \leq 10^9 $)，分别代表树的高度，砍掉这颗树需要的花费，这颗树的数量。

输出格式

对于每个测试用例，应输出最低成本。

输入输出样例

输入样例

输出样例

1
2

1
2

说明

题目中要求数目的高度必须严格大于

题解

~~场上没思路，场下看题解，这题我会啦，这题就是个B级题~~

说正题，题中要求最高的树的数量要大于所有树个数的一半。暴力？贪心？DP？主席树？场上都想过，都没有思路。这题有两种暴力方法一种 $O(n^2)$，另一种 $O(n*c)$，后者可过，所以这题成为了这一场的签到题，我怎么就没想到敲！但是既然是场下补题了就不写暴力了，太LOW。这题 $C$ 的数据范围完全可以出到 $10^9$。就按 $10^9$的数据范围写吧。

首先我们对这写树按照高度排序，从小到大去遍历这些树，对于第 $i$ 颗树，假设它就是这篇森林里面最高的树，那么对于当前这颗树

比它高的树全部砍去
比它矮的树砍去代价最少的使它满足题目要求

处理了这两个点这题就AC了。对于第一个点，记录一下后缀和，$v[i]$ 表示以 $i$ 颗树为最高树时砍到后面所有树所需要的花费。很容易想到，这肯定要预处理，这样第一个点就解决了。

对于第二个点，要找在比第 $i$ 颗树矮的树里面找到足够的数目保证题意并且花费最小。这里我们就可以开一个主席树，后者权值线段树。我选择了后者，但是看某篇题解好像说主席树简单好想一点？可我不会主席树难搞。就按权值线段树来写。对于权值线段树，我们维护两个值 $[1-i]$ 内树的数量和砍到这些树的代价和。向后进行枚举，到第i种树时，先把答案加上 $v[i+1]$ 表示如果第 $i$ 种树最高，那么它后面所有种类的树都要砍掉，然后去查询第$i$种树最高的情况下，前面最少需要砍掉树的代价是多少。需要注意的是多种树的高度相同的情况。
总时间复杂度 $O(n* \log c)$，对与 $C$ 是 $10^9$的数据范围，离散化后一样写。

总结一些自闭历程

全程要开 $long long$
ans的数据范围一开始一直没给够给了 $INF$ 一直没找到BUG 对比了半天题解发现开小了
还有就是代码比较长，容易多大或者少打一些符号，还是代码打的少。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+7;
typedef long long ll;
const long long INF = 0x7fffffff;
ll v[MAXN],n;
struct node {
    ll h,c,p;
    bool operator < (const node a)const {
        return a.h > h;
    }
} data[MAXN];

struct Node {
    ll l,r,val,num;
} T[MAXN << 2];

void PushUp(int rt) {
    T[rt].num = T[rt << 1].num + T[rt << 1|1].num;
    T[rt].val = T[rt << 1].val + T[rt << 1|1].val;
}

void Build(ll l,ll r,ll rt) {
    T[rt].l = l,T[rt].r = r;
    T[rt].val = T[rt].num = 0;
    if(l == r)
        return ;

    ll mid = (l + r) >> 1;
    Build(l,mid,rt << 1);
    Build(mid+1,r,rt << 1|1);
    PushUp(rt);
}

void Update(ll val,ll num,ll rt) {
    if(T[rt].l == T[rt].r) {
        T[rt].num += num;
        T[rt].val += (ll)num * (ll)val;
        return ;
    }

    ll mid = T[rt].l + T[rt].r >> 1;
    if(mid >= val)
        Update(val,num,rt << 1);
    else
        Update(val,num,rt << 1|1);
    PushUp(rt);
}

ll Query(ll rt,ll num) {
    if(num >= T[rt].num)
        return T[rt].val;
    if(T[rt].l == T[rt].r)
        return min(num*T[rt].l,T[rt].val);
    if(T[rt << 1].num >= num)
        return Query(rt << 1,num);
    else
        return T[rt << 1].val + Query(rt << 1|1,num - T[rt << 1].num);
}

void init() {
    memset(v,0,sizeof(v));
}

int main() {
    ios::sync_with_stdio(false);
    while(cin >> n) {
        init();
        ll l = INF,r = -1;
        for(int i = 1; i <= n; i++) {
            cin >> data[i].h >> data[i].c >> data[i].p;
            l = min((ll)l,data[i].c);
            r = max((ll)r,data[i].c);
        }
        sort(data+1,data+1+n);
        for(int i = n; i >= 1; i--)
            v[i] = v[i+1] + (data[i].c*data[i].p);
        Build(l,r,1);
        ll ans = 1e18,sum = 0;
        for(int i = 1; i <= n; i++) {
            int k;
            ll now = 0;
            for(k = 0; i+k <= n; k++) {
                if(data[i].h != data[i+k].h)
                    break;
                now += data[i+k].p;
            }
            k--;
            ll mid = v[i+k+1];
            if(sum >= now) {
                mid += Query(1,sum - now + 1);
            }
            ans = min(ans,mid);
            sum += now;
            for(int j = i; j <= i+k; j++) {
                Update(data[j].c,data[j].p,1);
            }
            i += k;
        }
        cout << ans << endl;
    }
    return 0;
}