G 점수를 달성하는 데 필요한 최소 점수를 알아내는 C++ 프로그램

두 개의 배열 p와 c가 있고 각 배열에는 D 요소가 있고 또 다른 숫자 G가 있다고 가정합니다. 프로그래밍 대회에서 각 질문은 난이도에 따라 점수가 매겨진다고 생각해 보세요. 질문 p[i]의 점수는 100i입니다. 이러한 p[1] + ... + p[D] 문제는 모두 경쟁에서 발생하는 문제입니다. 프로그래밍 웹사이트의 사용자는 숫자로 된 total_score를 가지고 있습니다. 사용자의 total_score는 다음 두 요소의 합입니다.

• 기본 점수: 해결한 모든 문제의 점수 합

• Reward: 사용자가 100i 점수로 모든 문제를 풀면 기본 점수에 더해 완벽한 보상 c[ i]를 얻게 됩니다.

Amal은 대회에 처음 참가했으며 아직 어떤 문제도 해결하지 못했습니다. 그의 목표는 종합 G학점 이상을 받는 것이다. 그가 이 목표를 달성하려면 최소한 얼마나 많은 문제를 해결해야 하는지 알아내야 한다.

입력이 G = 500; P = [3, 5]; C = [500, 800]이면 출력은 3

Steps

이 문제를 해결하기 위해 다음 단계를 따릅니다.

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;
}

Input

500, { 3, 5 }, { 500, 800 }

Output

3

위 내용은 G 점수를 달성하는 데 필요한 최소 점수를 알아내는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!