假设我们有两个数组p和c，每个数组都有D个元素，并且还有另一个数字G。考虑在编程竞赛中，每个问题的分数都基于其难度。问题p[i]的分数为100i。这些p[1] + ... + p[D]问题是竞赛中的所有问题。编程网站上的用户有一个数字total_score。用户的total_score是以下两个元素的和。
基础分数：解决的所有问题的分数之和
奖励：当用户解决所有分数为100i的问题时，除了基础分数外，还会获得完美奖励c[i]。
Amal是竞赛中的新手，还没有解决任何问题。他的目标是获得总分G或更多分。我们需要找到他至少需要解决多少问题才能达到这个目标。
立即学习“C++免费学习笔记（深入）”；
因此，如果输入是G = 500; P = [3, 5]; C = [500, 800]，那么输出将是3
步骤
为了解决这个问题，我们将按照以下步骤进行：
D := size of p
mi := 10000
for initialize i := 0, when i < 1 << D, update (increase i by 1), do:
sum := 0
count := 0
at := 0
an array to store 10 bits b, initialize from bit value of i
for initialize j := 0, when j < D, update (increase j by 1), do:
if jth bit in b is 1, then:
count := p[j]
sum := sum + ((j + 1) * 100 * p[j] + c[j]
Otherwise
at := j
if sum < G, then:
d := (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100)
if d <= p[at], then:
sum := sum + (at + 1)
count := count + d
if sum >= G, then:
mi := minimum of mi and count
return miExample
让我们看下面的实现以更好地理解−
#include <bits/stdc++.h>
using namespace std;
int solve(int G, vector<int> p, vector<int> c){
int D = p.size();
int mi = 10000;
for (int i = 0; i < 1 << D; i++){
int sum = 0;
int count = 0;
int at = 0;
bitset<10> b(i);
for (int j = 0; j < D; j++){
if (b.test(j)){
count += p.at(j);
sum += (j + 1) * 100 * p.at(j) + c.at(j);
} else {
at = j;
}
}
if (sum < G){
int d = (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100);
if (d <= p.at(at)){
sum += (at + 1) * 100 * d;
count += d;
}
}
if (sum >= G) {
mi = min(mi, count);
}
}
return mi;
}
int main() {
int G = 500;
vector<int> P = { 3, 5 };
vector<int> C = { 500, 800 };
cout << solve(G, P, C) << endl;
}Input
500, { 3, 5 }, { 500, 800 }输出
3
