数学コンテストの勝者を見つけるためのC++コード

サイズnの2つの配列PとTがあるとします。そして別の番号を持っているc。アマルとビマルは1つの数学コンテストに参加する予定です。 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