โปรแกรม C++ หาคะแนนขั้นต่ำเท่าไหร่ถึงจะได้คะแนน G

สมมติว่าเรามีสองอาร์เรย์ p และ c ทั้งคู่มีจำนวนองค์ประกอบ D แต่ละตัว และอีกจำนวนหนึ่ง G พิจารณาในการแข่งขันเขียนโค้ด แต่ละปัญหามีคะแนนตามความยาก ปัญหา p[i] มีคะแนน 100i ปัญหา p[1] + ... + p[D] เหล่านี้คือปัญหาทั้งหมดที่มีอยู่ในการแข่งขัน ผู้ใช้ในไซต์การเข้ารหัสมีจำนวน Total_score Total_score ของผู้ใช้คือผลรวมของสององค์ประกอบต่อไปนี้

• คะแนนฐาน :ผลรวมคะแนนของปัญหาที่แก้ไขทั้งหมด

• โบนัส :เมื่อผู้ใช้แก้ปัญหาทั้งหมดด้วยคะแนน 100i เขาหรือเธอจะได้รับโบนัสที่สมบูรณ์แบบ c[i] นอกเหนือจากคะแนนพื้นฐาน

Amal เป็นสมาชิกใหม่ในการแข่งขันและยังไม่สามารถแก้ไขปัญหาใดๆ ได้ วัตถุประสงค์ของเขาคือการได้คะแนนรวม G หรือมากกว่าคะแนน เราต้องหาอย่างน้อยว่าเขาต้องแก้ปัญหากี่ข้อเพื่อวัตถุประสงค์นี้

ดังนั้นหากอินพุตเป็นเหมือน G =500; พี =[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