SCUT校賽131：小P玩遊戲II（貪心 & 思維）

題目描述

小PP最近迷上了一個遊戲，但他在玩遊戲的時候遇到了一個問題。

小PP控制nn 個角色，标号為11到nn，小PP有KK個怪物可以配置設定給這nn個角色擊殺，一個怪物隻能配置設定給一個角色，并且必須要配置設定給一個角色。

對于第 i\,(1 \leq i \leq n)i(1≤i≤n)個角色，如果沒有配置設定到一個怪物，那麼它就會獲得經驗c_ic​i​​，如果配置設定到了t\,(t \geq 1)t(t≥1)個怪物，那麼它會獲得經驗a_i + t b_ia​i​​+tb​i​​。

小PP要把KK個怪物配置設定給這nn個角色，問所有角色獲得的經驗總和最多是多少。

輸入格式

輸入第一行一個整數TT，表示有TT組資料。

對于每組資料，第一行兩個正整數nn和KK。

接下來nn行，每行三個整數a_i,b_i,c_ia​i​​,b​i​​,c​i​​。

1 \leq T \leq 501≤T≤50

1 \leq n, K \leq 1000001≤n,K≤100000

1 \leq a_i, b_i, c_i \leq 1000001≤a​i​​,b​i​​,c​i​​≤100000

輸出格式

對于每組資料，輸出一個整數表示答案。

樣例資料

輸入

2
2 2
4 1 1
1 3 3
2 2
4 1 1
1 3 4      

輸出

9
10      

備注

思路：（參考題解和師兄的代碼）最佳配置設定的情況是這樣的，配置設定到>1隻怪的人一定<=1個，而這個人又是已配置設定到怪裡面的人b值最大的，其餘未配置設定到怪的人ai+bi-ci <= b，那麼這個人是誰無法确定，是以枚舉一下這個人就行。

# include <bits/stdc++.h>
# define ll long long
using namespace std;
const int maxn = 1e5;

struct node
{
    int a, b, c, d;
}m[maxn+3];

bool cmp(node x, node y)
{
    return x.d > y.d;
}

ll sum[maxn+3];
int main()
{
    int t, n, k;
    scanf("%d",&t);
    while(t--)
    {
        ll tot = 0;
        scanf("%d%d",&n,&k);
        for(int i=1; i<=n; ++i)
        {
            scanf("%d%d%d",&m[i].a, &m[i].b, &m[i].c);
            m[i].d = m[i].a + m[i].b - m[i].c;
        }
        sort(m+1, m+1+n, cmp);
        for(int i=1; i<=n; ++i)
            tot += m[i].c, sum[i] = sum[i-1] + m[i].d;
        ll ans = 0;
        for(int i=1; i<=n; ++i)
        {
            int l = 1, r = min(n,k-1);//k-1為上限是因為有一個怪已經配置設定給i了。
            while(l<=r)
            {
                int mid = l+r>>1;
                if(m[mid].d > m[i].b)
                    l = mid+1;
                else
                    r = mid-1;
            }
            if(r < i) ans = max(ans, (ll)tot + sum[r] + m[i].d + (ll)(k-r-1)*m[i].b);
            else ans = max(ans, (ll)tot + sum[r] + (ll)(k-r)*m[i].b);//這裡比較巧妙，當r==k-1時這樣處理貌似有bug，因為最佳可能是每個人分一個怪，但這裡剩下的一個怪強制分給i了，然而枚舉到最後一個人時又正确了。
        }
        printf("%lld\n",ans);
    }
    return 0;
}