codeforces 99999/553 Sultan's Pearls Solution 珍珠 题解

珍珠

题意

一共n课珍珠，m颗悬挂，其余在桌子上。如图所示。

仆人每天从某一端“借”一颗珍珠珠。主人每天都会检查悬挂的珍珠数目。

每颗珍珠的摩擦系数都是 $k$k.

若有 $w_h\>k{w}_t$wh​>kwt​，则珍珠落地，被主人发现。

珍珠 $i$i的质量是 $w_i$wi​,价格是 $c_i$ci​.

问仆人最大可以借多少价钱的珍珠，并输出借的珍珠数目和一种“借”的方案。

分析

增加限定条件

如果我们增加题目的限定条件，不允许从悬挂端取珍珠。显然，从左边能取的最大珍珠数有一个限度。并且符合单调性。即，如果可以取 $a$a颗，则一定可以取 $b(b\&lt;a)$b(b<a)颗；如果取 $a$a颗不行，则取 $b(b\&gt;a)$b(b>a)一定不行。故可以二分。
当然，如果只是如此的话，直接枚举比二分划算，因为每次求 $w_t$wt​的代价是线性的，除非预先线性求出前缀和，之后可以 $\Theta \left(1\right)$Θ(1).

去掉限定条件

现在假设我们通过一系列合法的操作已经去掉了若干颗悬挂端末尾的珍珠，达到了末尾珠子是 $end$end号的状态。然后加上上面所述的限定条件，则在这种状态下的最优情况由以上可知可以二分求得。
如此来看，我们还需要解决的问题有：

1. 状态仅由结尾珠子是 $end$end表示知否足够？即如此做是否考虑了所有情况？
2. 如何确定状态是否可由合法操作得到。

对于1，事实是足够的。 $end$end确定了，悬挂的珠子就确定了，即 $w_h$wh​确定了，那么能躺在桌子上的最后的极限情况就是不变的。因为每颗珠子质量非负，因此在这个状态是可达的情况下，在达到这个状态之前去除左边的还是达到之后去除从效果上来看没有差异。因此结尾为 $end$end，开头只需要设置为1号即考虑了所有情况。

对于2，因为珠子质量非负，可以肯定的是左边桌子端一颗不能少。因为不可能这么存在一种情况。
两种情况 $S_1,S_2$S1​,S2​的珠子，除了 $S_1$S1​比 $S_2$S2​左边少了几颗，剩余的从右边看都是一样的。而 $S_1$S1​经过一番合法操作可以到达末尾为 $end$end号珠子的状态，而 $S_2$S2​却无法到达。事实上，如果 $S_1$S1​可以，只要 $S_2$S2​抄 $S_1$S1​的操作就一定可以。
知道了以上这点，显然我们的操作就无需选择了，只剩下不断的取下珠子，直到结尾是 $end$end即可。然后需要保证每一步取完都是不会落地的。因此，从后往前枚举end，尝试取就好。

Code

#include <bits/stdc++.h>
using namespace std;

class Sum
{
private:
    vector<int> sum;

public:
    Sum()
    {
    }

    void set(vector<int> &val)
    {
        sum.clear();
        if (val.empty())
            return;
        sum.push_back(val[0]);
        int sz = val.size();
        for (int i = 1; i < sz; ++i)
            sum.push_back(sum[i - 1] + val[i]);
    }

    inline int get_sum(int i)
    {
        return i >= 0 ? sum[min<int>(i, sum.size())] : 0;
    }

    // sum[l..r]
    inline int get_sum(int l, int r)
    {
        return get_sum(r) - get_sum(l - 1);
    }

    void print()
    {
        for (auto x : sum)
            cout << x << " ";
        cout << endl;
    }
};

class Pearls
{
private:
    int total_cnt;
    int hang_cnt;
    int k;
    vector<int> weight;
    vector<int> cost;
    Sum w;
    Sum c;
    struct Ans
    {
        int l;
        int r;
        int cost;
        bool valid;
        void update(int l0, int r0, int cost0)
        {
            if (valid)
            {
                if (cost0 > cost)
                {
                    l = l0;
                    r = r0;
                    cost = cost0;
                }
            }
            else
            {
                l = l0;
                r = r0;
                cost = cost0;
                valid = true;
            }
        }
        void print()
        {
            cout << l + r << " " << cost << endl;
            string s(r,'H');
            string ss(l,'T');
            cout<<s<<ss<<endl;
        }
    }ans;

public:
    void init()
    {
        cin >> total_cnt >> hang_cnt >> k;
        weight.resize(total_cnt + 1);
        cost.resize(total_cnt + 1);
        weight[0] = cost[0] = 0;
        for (int i = 1; i <= total_cnt; ++i)
        {
            cin >> weight[i] >> cost[i];
        }
        w.set(weight);
        c.set(cost);
    }
    void work()
    {
        int w_h;
        int w_t;
        int table_end;
        for (int end = total_cnt; end >= hang_cnt; --end)
        {
            table_end = end - hang_cnt;
            w_h = w.get_sum(table_end + 1, end);
            w_t = w.get_sum(1, table_end);
            if (w_h > k * w_t)
            {
                // 前面一颗珠子不少仍旧无法实现这个状态的平衡，则无法实现。
                // 因为end更小的无法绕过这一end的状况。所以更小的end也无需考虑。
                break;
            }
            int l = 1;             // is ok 可以维持平衡
            int r = table_end + 1; // is not ok 不可以维持平衡
            while (r - l > 1)
            {
                int m = l + (r - l) / 2;
                w_t = w.get_sum(m, table_end);
                if (w_h <= k * w_t)
                { // m is ok
                    l = m;
                }
                else
                {
                    r = m;
                }
            }
            ans.update(l-1, total_cnt - end, c.get_sum(1, l - 1) + c.get_sum(end + 1, total_cnt));
        }
        ans.print();
    }
};

int main()
{
    Pearls *p = new Pearls();
    p->init();
    p->work();
    delete p;
    return 0;
}