資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式找出至少需要多少分數才能獲得G分
假設我們有兩個陣列p和c，它們都包含D個元素，還有一個數字G。考慮在一個編碼競賽中，每個問題的得分都基於難度。問題p[i]的得分為100i。這些p[1] + ... + p[D]個問題是競賽中存在的所有問題。編碼網站中的使用者有一個分數total_score。使用者的total_score是以下兩個元素的總和。
基礎分數：所有已解決問題的分數之和
獎勵：當用戶解決所有得分為100i的問題時，除了基礎分數外，他/她還會獲得完美的獎勵c[i]。
Amal是競賽新手，還沒有解決任何問題。他的目標是獲得G分或更高的分數。我們必須找到為了達到這個目標，他至少需要解決多少個問題。
因此，如果輸入類似於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 mi示例
讓我們看看以下實現，以便更好地理解：
#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;
}輸入
500, { 3, 5 }, { 500, 800 }輸出
3
更新於： 2022年3月2日
237 次檢視
廣告