In this HackerEarth The score game problem solution You are given an array A of N elements where each element is a pair represented by (X[i], Y[i]).
Bob and Alice play a game where both of them have to pick some elements from the array A. Suppose, Bob picked the elements at index i1,i2,...,ik where K <= N.
Score(Bob) = Sigma(X[j] + Y[j]), where j belongs to (i1,i2,....,ik).
Score(Alice) = Sigma(X[j]), where j belongs to (1,2,....,N) excluding (i1,i2,....,ik).
Find the minimum number of elements Bob must pick such that the score of Bob is greater than Alice.
HackerEarth The score game problem solution.
#include<bits/stdc++.h>
#define int long long int
using namespace std;
bool cmp(pair<int,int> a, pair<int,int> b)
{
int gaina = 2*a.first + a.second;
int gainb = 2*b.first + b.second;
if(gaina != gainb) return gaina < gainb;
return a.first < b.first;
}
void solve(){
int n;
cin >> n;
int x[n+1], y[n+1];
for(int i = 1 ; i <= n ; i++) cin >> x[i];
for(int i = 1 ; i <= n ; i++) cin >> y[i];
int bob = 0;
int alice = 0;
vector<pair<int,int> >m;
for(int i = 1 ; i <= n ; i++){
m.push_back(make_pair(x[i], y[i]));
alice += x[i];
}
sort(m.begin(), m.end(), cmp);
int answer = 0;
for(int i = n - 1 ; i >= 0 ; i--)
{
if(bob > alice) break;
answer++;
bob += (m[i].first + m[i].second);
alice -= (m[i].first);
}
cout << answer << endl;
}
signed main(){
int t;
cin >> t;
while(t--){
solve();
}
}
Second solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
int x[MAX_N], y[MAX_N];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
ll alice = 0;
for (int i = 0; i < n; ++i) {
cin >> x[i];
alice += x[i];
}
for (int i = 0; i < n; ++i)
cin >> y[i];
int per[n];
iota(per, per + n, 0);
sort(per, per + n, [](int i, int j) { return 2 * x[i] + y[i] > 2 * x[j] + y[j]; });
ll me = 0;
int ans = 0;
while (me <= alice) {
me += x[per[ans]] + y[per[ans]];
alice -= x[per[ans++]];
}
cout << ans << '\n';
}
}
0 Comments