hyz's blog
0%

发表于

题意

你拥有n个怪兽，每个怪兽具有hp和dam这两种属性。你可以进行两种操作：第一种是将怪兽的hp值翻倍；第二种是令怪兽的dam = hp。第一种操作你最多可以进行a次，第二种操作你最多可以进行b次，问所有怪兽的dam和最大是多少？

分析

看到题目，容易想到动态规划，但是想了挺久，没思路。看了官方题解，发现了一个重要的性质：第一种操作应该只分配给某一只怪兽，这个可以通过反证法来证明，挺简单的，这里不再赘述。a个第一种操作和1个第二种操作分配完了，那么剩余的b-1个第二种操作应该怎么分配？贪心，即优先分配给hp - dam值较大的怪兽（在这之前需要排序一次）。最终此题的复杂度是O(nlogn)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

ll n, aa, b, t, ans, sum;

struct node {
    ll hea, dam;
}a[N];

bool cmp(node a, node b) {
    return (a.hea - a.dam) > (b.hea - b.dam);
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n >> aa >> b) {
        t = 1;
        while(aa--) t *= 2;
        for(int i = 0; i < n; i++)
            scanf("%lld%lld", &a[i].hea, &a[i].dam);
        sort(a, a + n, cmp);
        for(int i = 0; i < n; i++) {
            if(i < b) sum += max(a[i].hea, a[i].dam);
            else sum += a[i].dam;
        }
        if(b == 0) {
            printf("%lld\n", sum);
            continue;
        }
        for(int i = 0; i < n; i++) {
            if(i < b) ans = max(ans, sum - max(a[i].hea, a[i].dam) + max(a[i].hea * t, a[i].dam));
            else ans = max(ans, sum - max(a[b-1].hea, a[b-1].dam) + a[b-1].dam - a[i].dam + max(a[i].hea * t, a[i].dam));
        }
        printf("%lld\n", ans);
    }

    return 0;
}