贪心 | Hexo

P2240 部分背包问题

纯 C++11 风格的代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n, m;  cin >> n >> m;
    vector<pair<double, pair<int, int> > > coins(n);
    for (auto &c : coins) {
        cin >> c.second.first >> c.second.second;
        c.first = (double)c.second.second/c.second.first;
    }
    sort(coins.begin(), coins.end(), greater<pair<double, pair<int, int> > >());
    double ans = 0;
    for (auto &c : coins) {
        if (c.second.first > m) ans += m * c.first;
        else ans += c.second.second;
        m -= c.second.first;
        if (m < 0) break;
    }
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}

枚举+贪心

A. Boboniu Chats with Du

枚举天数，然后用前缀和 \(O(1)\)来解每个的答案，然后取最大值

RPG Protagonist

枚举第一个人装多少个重量最小的装备。然后第二个人装剩下的知道装不下为止。然后取每次枚举的最大值

Zigzags

我们可以用前缀和表示某个区间有多少个 \(i\) 出现。所以我们可以枚举中间的两个下标，确定 \(y,x\)，统计前面出现了多少个 \(x\) ，后面出现了多少个 \(y\).

数学+贪心

1393C.Pinkie Pie Eats Patty-cakes

可以构造一个最优解。影响答案的只有最大的那个。所以先求出最多个数 \(mx\) 是多少, 然后求出 \(mx\) 的个数 \(nx\). 那么答案就是把最大的那么一个个排列，然后把剩余的插入其中的空隙。也就是 \((n-mx \cdot nx)/(mx-1) + nx - 1\)

前缀和+贪心

B. Negative Prefixes

贪心