Twins 160A

In this problem, two twins have to divide some coins. One of them wants to take a strictly larger amount of money than the other twin. Equal is not enough, even being 1 unit greater is fine.

Also, he wants to do it using the minimum number of coins. Maybe so that when the other twin wakes up and counts the coins, it doesn't look too suspicious. Although this is definitely unethical, our job is to solve the problem, not judge the twin.

So we need to find the minimum number of coins he has to take so that his total value becomes strictly greater than the value left for the other twin.

Approach:

Since we have to find a minimum, greedy immediately comes to mind. And the twin is greedy too (≧▽≦q), so a greedy solution feels appropriate.

At first, I thought about what would help us reach a larger sum using the fewest coins possible. Taking small coins doesn't make much sense because we would need many of them. To maximize the amount gained per coin, we should always take the largest available coin first.

So I sort the coins in descending order.

Then I keep taking coins from the front and maintain the sum of the coins I have taken. The moment my collected sum becomes strictly greater than the sum of the remaining coins, I stop.

Since I always pick the largest coin available first, I reach the required amount using the fewest possible coins.

#include<bits/stdc++.h>
using namespace std;
 
    typedef  long long   ll;
    typedef vector<int> VI;
    typedef vector< long long  > VLL;
    typedef vector<bool> VB;
    
 

    #define inp(v) for (auto& x : v) cin >> x
    
    void solve();
  int  main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifdef LOCAL
    cerr << "Execution time: " << 1000.f * clock() / CLOCKS_PER_SEC << " ms." << nl;
    #endif
    
        solve();
    
    return 0;
}
void solve() {
    ll c;
    cin >> c;
    VLL coin(c);
    inp(coin);
    ll add = accumulate(coin.begin(), coin.end(),0ll);
    sort(coin.begin(), coin.end(), greater<ll>());
    ll g=0;
    ll add2 = 0;
    for ( ll i = 0; i < c;i++){
        g++;
        add2 += coin[i];
        if(add2>(add-add2))
            break;
    }
    cout <<g ;
}

Complexity:

Sorting takes O(n log n).

The traversal is O(n).

So the overall complexity is O(n log n).