Giải bài ntucoder VASU - Vắt sữa bò

Link bài:

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;
}

void run(){
    sort(a+1, a+n+1);
    repdec(n, 1){
        if (a-(n-i) > 0) ans += a-(n-i);
        else continue;
    }
    cout << ans;
}
int main(){
    read();
    run();
    return 0;
}