3386
22
Link bài:
Thuật toán:
VD: Với 3 con bò có trữ lượng sữa lần lượt là 1 2 3 lít.
Nếu vắt lần lượt từ bé đến lớn, ta sẽ thu được lần lượt là 1 lít ở con thứ nhất, 1 lít ở con thứ 2 (do bị hoảng 1 lần) và 1 lít ở con thứ 3 (bị hoảng 2 lần). Nếu vắt theo thứ tự ngược lại, ta sẽ nhận được 3 lít ở con số 1, 1 lít ở con thứ 2 (Bị hoảng 1 lần) và không có gì ở con thứ 3. Trường hợp 2 ta thu được nhiều sữa hơn hẳn.
Code:
Thuật toán:
- Ta sẽ vắt các con bò theo thứ tự từ nhiều sữa nhất đến ít sữa nhất.
- Nếu vắt những con bò ít sữa hơn thì những con bò nhiều sữa hơn sẽ bị giảm lượng sữa rất nhiều (Tối đa n-1 lít) trong khi nếu để những con bò ít sữa vắt cuối cùng, chúng có hết sữa giữa chừng cũng không làm hao hụt gì thêm.
VD: Với 3 con bò có trữ lượng sữa lần lượt là 1 2 3 lít.
Nếu vắt lần lượt từ bé đến lớn, ta sẽ thu được lần lượt là 1 lít ở con thứ nhất, 1 lít ở con thứ 2 (do bị hoảng 1 lần) và 1 lít ở con thứ 3 (bị hoảng 2 lần). Nếu vắt theo thứ tự ngược lại, ta sẽ nhận được 3 lít ở con số 1, 1 lít ở con thứ 2 (Bị hoảng 1 lần) và không có gì ở con thứ 3. Trường hợp 2 ta thu được nhiều sữa hơn hẳn.
Code:
Mã:
#include <bits/stdc++.h>
#define repinc(k, n) for (int i = k; i <= n; i++)
#define repdec(n, k) for (int i = n; i >= k; i--)
using namespace std;
int n, ans;
int a[1007];
void read(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("VASU.INP", "r", stdin);
//freopen("VASU.OUT", "w", stdout);
cin >> n;
repinc(1, n) cin >> a[i];
}
void run(){
sort(a+1, a+n+1);
repdec(n, 1){
if (a[i]-(n-i) > 0) ans += a[i]-(n-i);
else continue;
}
cout << ans;
}
int main(){
read();
run();
return 0;
}
