CF 913 二进制背包 贪心/二分背包

A

B

C

给你N(N<=30)种水瓶每种水瓶有无限个 每个的体积是2^(i-1)价格是cost[i] 要求你花最少的钱弄出L体积的水

先从前到后扫一遍cost[i+1]=min(cost[i+1],cost[i]*2)  再从后往前扫一遍cost[i]=min(cost[i],cost[i+1) 保证了价格的最优化

然后从0开始到30 如果二进制有当前体积的就买 同时检验一下anser=min(anser,cost[i+1])（意思是如果买当前所有体积两倍的水比买当前的便宜就买当前体积两倍的）

#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int n;
ll L;
ll cost[35];
int main()
{
        cin >> n;
        cin >> L;
        for (int i = 1; i <= n; i++)
        {
                cin >> cost[i];
        }
        for (int i = 1; i <= n - 1; i++)
        {
                cost[i + 1] = min(cost[i + 1], cost[i] * 2);
        }
        for (int i = n - 1; i >= 1; i--)
        {
                cost[i] = min(cost[i], cost[i + 1]);
        }
        for (int i = n + 1; i <= 33; i++)
        {
                cost[i] = cost[i - 1] * 2;
        }
        ll anser = 0;
        for (int i = 0; i <= 30; i++)
        {
                if (L & (1LL << i))
                {
                        anser += cost[i + 1];
                }
                anser = min(anser, cost[i + 2]);
        }
        cout << anser << endl;
}

D

给你N个问题 T时间 每个问题有一个ai和ti 分别的意思是 总解决的问题如果不大于ai这个问题就有一个贡献与问题所消耗的时间

要求你求出最大的贡献值

可以二分也可以直接优先队列贪心 把ai ti i的问题 push进 pro[ai] make_pair(ti,i)

假设当前最大值是i 从N开始 把pro[i]的全部压入优先队列 如果问题数比i大就 pop掉最大的 直到遇到符合要求的或者i==0

#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, int> > ke[200005];
priority_queue<pair<int, int> > que;
int main()
{
        int n, T;
        cin >> n >> T;
        int where, t;
        for (int i = 1; i <= n; i++)
        {
                scanf("%d %d", &where, &t);
                ke[where].push_back(make_pair(t, i));
        }
        int anser = 0;
        int sum = T;
        for (int i = n; i >= 0; i--)
        {
                for (pair<int, int> ch : ke[i])
                {
                        que.push(ch);
                        sum -= ch.first;
                }
                while (que.size() > i)
                {
                        sum += que.top().first;
                        que.pop();
                }
                if (que.size() == i && sum >= 0)
                {
                        cout << i << endl << i << endl;
                        while (que.size())
                        {
                                cout << que.top().second << " ";
                                que.pop();
                        }
                        cout << endl;
                        return 0;
                }
        }
}