2017杭电ACM集训队单人排位赛 - 6 [Problem 1009]

201707 （ACM）思维

题意

• n个角色，标号为1到n,有K个怪物可以分配给这n个角色击杀，一个怪物只能分配给一个角色，并且必须要分配给一个角色。
• 对于第i个角色，如果没有分配到一个怪物，那么它就会获得经验ci，如果分配到了t(t>=1)个怪物，那么它会获得经验ai+tbi。
• 把K个怪物分配给这n个角色，问所有角色获得的经验总和最多是多少。

题解

• 首先分配到的怪兽数量大于一个的角色最多只有一个。
  
  • 反证法：假设有一个以上，那么肯定有一个角色的b值最大，所以分配给这个角色就行了。
• 枚举怪兽数量大于一个的角色i。
  
  • 对于当前的一个怪兽，如果分配给其他角色j获得的a[j]+b[j}-c[j]>b[i]，那么分配给这个角色就行了。
• 所以按照a[j]+b[j}-c[j]排序，维护前缀和。枚举i的时候二分j的范围。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
//---------------
const int N=100005;
struct Node {
    int a,b,c,val;
    bool operator < (const Node &tmp) const {
        return val>tmp.val;
    }
}nn[N];
int n,k;
ll sumv[N];
int bin(int x) {
    int ans=0,l=1,r=n;
    while(l<=r) {
        int m=(l+r)>>1;
        if(nn[m].val>x) {
            ans=m;
            l=m+1;
        } else {
            r=m-1;
        }
    }
    return ans;
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d%d",&n,&k);
        ///read
        ll sumc=0;
        rep(i,1,n+1) {
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
            nn[i]={a,b,c,a+b-c};
            sumc=sumc+c;
        }
        ///get sum
        sort(nn+1,nn+n+1);
        rep(i,1,n+1) sumv[i]=sumv[i-1]+nn[i].val;
        ///solve
        ll ans=0;
        rep(i,1,n+1) {
            int p=bin(nn[i].b);
            p=min(p,k);
            ll res=0;
            if(i<=p) {
                res=sumc+sumv[p]+1ll*(k-p)*nn[i].b;
            } else {
                if(p==k) --p;
                res=sumc+sumv[p]+nn[i].val+1ll*(k-p-1)*nn[i].b;
            }
            ans=max(ans,res);
        }
        ///print 
        printf("%lld\n",ans);
    }
    return 0;
}