2019牛客夏季多校訓練キャンプ(第7回)

27276 ワード

C題:

題意:n種の木を与え、各木は高さに対応し、必要なお金と数量を切り落とした.今聞いて、最も少ないお金を使って、すべての高さの最も高い木のと陽今樹の総和の半分より大きい(厳格)

は、重みセグメントツリーを使用して書きます.ツリーの高さがxに等しい場合、現在の費用をどのように計算するかを考えてみましょう.まずすべての木の高さがxに等しいことを統計すると、この時xは最も高いので、xより大きいものはすべて切り捨て、xより小さい木は、数がx-1に等しいまで切り落とすだけです.では、まず高さに基づいてソートすることができます.現在より高い木を切り落とすことができます.費用は接尾辞を求めるのと同じです.問題は、高さxよりも小さな木を動的に維持し、どのように切るかです.私たちはcostをノードとする重み線分ツリーを開き、現在の高さを維持し、すべてのツリーがcost位置のnumsの和を維持します.では、高さxの小さいツリーを維持するときは、貪欲に左側、すなわちcostの小さい位置から取り始め、sum-x+1個を取るだけでいいです.これが切り落とす最小値です.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#include
#define up(i,a,b)  for(int i=a;i
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
int read()
{
    char ch = getchar(); int x = 0, f = 1;
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
typedef pair<int, int> pir;
struct node { ll cost, num; };
int n;
const int N = 205;
ll nums[4 * N], cost[4 * N];
vector<int >vec;
void pushup(int root)
{
    nums[root] = nums[root << 1] + nums[root << 1 | 1];
    cost[root] = cost[root << 1] + cost[root << 1 | 1];
}
void update(int root, int l, int r, int pos, ll k)
{
    if (l == r)
    {
        nums[root] += k;
        cost[root] += k * 1ll * pos;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos > mid)update(root << 1 | 1, mid + 1, r, pos, k);
    else update(root << 1, l, mid, pos, k);
    pushup(root);
}
ll querry(int root, int l, int r,ll k)
{
    if (k <= 0)return 0;
    if (l == r)
    {
        return 1ll * l*k;
    }
    int mid = (l + r) >> 1;
    if (nums[root << 1] >= k)
    {
        return querry(root << 1, l, mid, k);
    }
    else
    {
        return cost[root << 1] + querry(root << 1 | 1, mid + 1, r, k - nums[root << 1]);
    }
}
int main()
{
    while (cin >> n)
    {
        map < ll, vector < node > > mp;
        memset(cost, 0, sizeof(cost));
        memset(nums, 0, sizeof(nums));
        vec.clear();
        up(i, 0, n)
        {
            int x, y, z;
            x = read(), y = read(), z = read();
            mp[x].push_back(node{ y,z });
            vec.push_back(x);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        ll sum = 0;
        for (auto i : vec)
        {
            for (auto k : mp[i])
            {
                update(1, 1, 200, k.cost, k.num);
                sum += k.num;
            }
        }
        ll ans = 1e18;
        ll sufix = 0;
        dwd(i, vec.size()-1, 0)
        {
            ll tempsum = 0;
            ll tempcost = 0;
            for (auto k : mp[vec[i]])
            {
                tempsum += k.num;
                tempcost += 1ll * k.num*k.cost;
                update(1, 1, 200, k.cost, -k.num);
            }
            sum -= tempsum;
            ans = min(ans, sufix + querry(1, 1, 200, sum - tempsum + 1));
            sufix += tempcost;
        }
        cout << ans << endl;
    }
    return 0;
}

ZOJ 1377 Grandpa's Estate

Google Cloud Data Platform Day　セミナーメモ