PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mamaleshrh
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting
PROBLEM:
You have N table legs, the i-th of which can support weight W_i.
When an object is placed on a table, its weight is distributed equally to all the legs supporting it.
What’s the maximum possible weight that can be placed on a table by choosing some subset of the legs?
EXPLANATION:
Suppose we choose exactly k legs out of the N we have. What’s the maximum weight they can handle, and which k legs should we choose?
Clearly, it’s best to choose the k legs with maximum W_i; after all, if any k legs can support some weight, these k surely can.
For convenience, let’s sort the legs by descending order of supporting weight, i.e,
W_1 \geq W_2 \geq W_3 \geq\ldots\geq W_N.
Then, if we choose exactly k legs, the observation above says it’s best to choose \{W_1, W_2, \ldots, W_k\}.
Now, suppose we place a weight of X on the table formed by these legs.
X will be distributed equally to all the tables, meaning each of them will receive a weight of \frac{X}{k}.
Each leg should be able to withstand this; meaning each of W_1, W_2, \ldots, W_k should be \geq \frac{X}{k}.
In particular, it’s enough if W_k \geq \frac{X}{k}; since it’s the “weakest” leg - if it can withstand the weight, the others definitely can too.
This tells us that X \leq k\cdot W_k.
Clearly, the maximum load that can be placed is exactly k\cdot W_k.
To finish up, simply try this for every possible value of k.
That is, the answer is
Of course, this is after sorting the W_i in descending order.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
//#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>//oset name name.order_of_key(#ele<k) *name.find_by_order(index) less_equal greater greater_equal
#define vi vector<int>
#define pii pair<int,int>
#define mii map<int,int>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define int long long
#define ld long double
#define pb push_back
#define all(v) v.begin(), v.end()
#define back(v) v.rbegin(), v.rend()
#define yes cout << "YES" <<"\n";
#define no cout << "NO" <<"\n";
#define deb(a) cerr<< #a << "=" << (a)<<"\n";
#define nl "\n"
#define FastIO \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
using namespace std;
#define mod 1000000007
const int oo = 1e18;
void solve()
{
int n;cin>>n;
vi as(n);
for(int i=0;i<n;i++){
cin>>as[i];
}
sort(all(as));
reverse(all(as));
int out=0;
for(int i=0;i<n;i++){
out=max(out,as[i]*(i+1));
}
cout<<out<<nl;
}
signed main()
{
FastIO;
// freopen("P4_6.in", "r", stdin);
// freopen("P4_6.out", "w", stdout);
int test=1;
cin >> test;
while (test--)
{
solve();
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
for i in range(n): ans = max(ans, (n-i)*a[i])
print(ans)