【P5961】 [BalticOI 2006] coin collector钱币收藏家 题解

· · 题解

P5961 [BalticOI 2006] coin collector钱币收藏家

思路

像这种题，直接用贪心。

对于局部最优解 a,b，如果想要让下一局部最优解加入 c，应满足 a+b≥c（情况 1），否则忽略 c（情况 2）。

另：

  1. 为了更加方便地存储最优解，推荐用 vector 来存储。

  2. 这道题可以在输入时就进行处理，对结果不会有影响。

复杂度

只用在输入时处理，复杂度 \mathcal{O}(n)。

局部代码（参考）

情况 1

if (s >= c) {
    s -= v[(int)v.size() - 1];
    v.pop_back();       
}

情况 2

if (s + c >= k) break;

完整代码

#include <bits/stdc++.h>
//#define int long long
#define LL long long
#define FR q.front()
using namespace std;
const int MAXN = 1e3 + 10;
int a[MAXN], n, m;
LL ans = 0;
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch<'0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
LL s = 0;
vector<int>v;
signed main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    int T; int c, d,k;
    n = read(); k = read();
    for (int i = 1; i <= n; i++) {
        cin >> c >> d;
        if (s >= c) {
            s -= v[(int)v.size() - 1];
            v.pop_back();

        }
        if (d == 0) {
            if (s + c >= k) break;
            else v.push_back(c), s += c;
        }
    }
    if (s == 0) s = 1;
    write((int)v.size());
    printf("\n");
    write(k - s);
    return 0;
}