四项一起对得上吗
运行下面这段程序:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int greedy(const vector<int>& cs, int t) {
// 面值已按从大到小给好:每次拿不超过剩下金额的最大面值
int n = 0;
for (int c : cs) {
while (t >= c) {
t -= c;
n++;
}
}
return n;
}
int best(const vector<int>& cs, int t) {
// dp[a] = 凑够 a 最少要几枚
const int INF = 1000000000;
vector<int> dp(t + 1, INF);
dp[0] = 0;
for (int a = 1; a <= t; a++) {
for (int c : cs) {
if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
}
}
return dp[t];
}
struct Seg {
int s, e;
};
template <class Cmp>
int sched(vector<Seg> iv, Cmp cmp) {
// 按 cmp 排好,从头挑,不重叠就要
stable_sort(iv.begin(), iv.end(), cmp);
int last_end = -1;
int n = 0;
for (const Seg& x : iv) {
if (x.s >= last_end) {
n++;
last_end = x.e;
}
}
return n;
}
int wait_total(const vector<int>& order) {
// 按给定顺序做任务:把每个任务的完成时刻加起来
int t = 0;
int s = 0;
for (int x : order) {
t += x;
s += t;
}
return s;
}
int main() {
vector<int> w = {4, 1, 3, 2};
sort(w.begin(), w.end());
bool ok = greedy({25, 10, 5, 1}, 63) == 6 && best({4, 3, 1}, 6) == 2
&& sched({{1, 4}, {2, 3}, {3, 5}, {0, 7}, {5, 6}, {6, 8}}, [](const Seg& a, const Seg& b) { return a.e < b.e; }) == 4 && wait_total(w) == 20;
cout << boolalpha << ok << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)
全部评论