수학 경시 대회 우승자를 찾는 C++ 코드

크기가 n인 두 개의 배열 P와 T가 있다고 가정합니다. 그리고 다른 숫자가 있습니다. c. Amal과 Bimal은 하나의 수학 경시 대회에 참가할 예정입니다. n개의 문제가 있습니다. i번째 문제는 초기 점수 P[i]를 가지며 T[i]를 사용하여 해결합니다. P와 T는 모두 오름차순으로 정렬됩니다. 여기서 c는 잃는 점에 대한 상수입니다. x 시간(컨테스트 시작 후 x분)에 문제가 제출되면 max(0, P[i] - c*x) 포인트가 제공됩니다. Amal은 1, 2, ... n의 순서로 문제를 풀고 Bimal은 n, n-1, ... 1과 같이 문제를 풉니다. 누가 최고 점수를 받을지 찾아야 합니다. 그들이 같은 것을 가지고 있다면 그것은 '동점'이 될 것입니다.

따라서 입력이 c =2와 같으면; P =[50, 85, 250]; T =[10, 15, 25]이면 출력은 Amal이 됩니다.

단계

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

n := size of P
m := 0
ans1 := 0
ans2 := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   m := m + T[i]
   ans1 := ans1 + maximum of (0, P[i] - c * m)
m := 0
for initialize i := n - 1, when i > 1, update (decrease i by 1), do:
   m := m + T[i]
   ans2 := ans2 + maximum of (0, P[i] - c * m)
if ans1 > ans2, then:
   return "Amal"
otherwise when ans1 < ans2, then:
   return "Bimal"
Otherwise
   return "Tie"

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
string solve(int c, vector<int> P, vector<int> T){
   int n = P.size();
   int m = 0, ans1 = 0, ans2 = 0;
   for (int i = 0; i < n; i++){
      m += T[i];
      ans1 += max(0, P[i] - c * m);
   }
   m = 0;
   for (int i = n - 1; i > 1; i--){
      m += T[i];
      ans2 += max(0, P[i] - c * m);
   }
   if (ans1 > ans2)
      return "Amal";
   else if (ans1 < ans2)
      return "Bimal";
   else
      return "Tie";
}
int main(){
   int c = 2;
   vector<int> P = { 50, 85, 250 };
   vector<int> T = { 10, 15, 25 };
   cout << solve(c, P, T) << endl;
}

입력

2, { 50, 85, 250 }, { 10, 15, 25 }

출력

Amal