Chênh lệch tối đa có thể đạt được bằng cách chọn một nửa số lá bài có giá trị nhỏ nhất cho một người, và phần còn lại được chọn cho người kia.

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;
    int a[n];
    for(int &i : a) cin >> i;
    sort(a, a + n);
    int x = 0, y = 0;
    for(int i=0; i<n; i++){
        if(i < n / 2) x += a[i];
        else y += a[i];
    }
    cout << y - x;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ cần sắp xếp lại mảng các số này, tuy nhiên, nếu ta sắp xếp theo thứ tự giảm dần thì rất có thể sẽ gặp phải trường hợp

$$$a = [321, 32] \to 32132$$$ nhưng nó sẽ nhỏ hơn việc ta ghép ngược lại là $$$32321$$$.

Như vậy, ta sẽ cần sắp xếp theo tiêu chí số dứng trước nối với số đứng sau phải lớn hơn phép nối ngược lại.

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;
    string a[n];
    for(auto &i : a) cin >> i;
    sort(a, a + n, [](string a, string b){
        return a + b > b + a;
    });
    for(auto &i : a) cout << i;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta có nhận xét rằng khi độ chênh lệch là nhỏ nhất thì tức là tập hợp $$$k$$$ phần tử đó là các giá trị gần nhau nhất có thể.

Hay có thể hiểu là khi ta sắp xếp lại mảng $$$a$$$ thì tập hợp đó sẽ là $$$1$$$ trong những đoạn con độ dài $$$k$$$ của mảng.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

void solve(){
    int n, k; cin >> n >> k;
    int a[n+1];
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    int res = 2e9;
    for(int i=1; i<=n-k+1; i++){
        res = min(res, a[i + k - 1] - a[i]);
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Đây thực chất là bài toán Nối dây mà các bạn làm ở trên Code PTIT.

Ta có thể tư duy theo hướng ghép lại $$$n$$$ thanh gỗ đó trở lại ban đầu, tức là ghép $$$2$$$ đoạn gỗ dài $$$u$$$ và $$$v$$$ thì sẽ tốn $$$u + v$$$ đơn vị tiền.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define int long long 

void solve(){
    int n; cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=1; i<=n; i++){
        int x; cin >> x;
        q.push(x);
    }
    int res = 0;
    while(q.size() > 1){
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();
        q.push(x + y);
        res += x + y;
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Thao tác đề bài đã cho có thể giúp ta sắp xếp lại mảng theo cách tuỳ ý. Như vậy, ta cần sắp xếp sao cho các phần tử cách nhau $$$k$$$ đơn vị có giá trị chênh lệch nhau là nhỏ nhất.

Tuy nhiên, để việc chuyển suy nghĩ đó vào code trở nên đơn giản thì ta sẽ sắp xếp lại mảng:

Xét ví dụ $$$1$$$, ta có $$$a = [5, 2, 7, 1, 10, 3] \to a = [1, 2, 3, 5, 7, 10]$$$.

Sau đó, ta sẽ coi $$$1$$$ ở vị trí $$$1$$$, duyệt qua các số ngay phía sau và gán cho nó vị trí $$$1 + k$$$ tức là $$$2$$$ sẽ ở vị trí $$$1 + k$$$. Cứ như vậy thì số $$$3$$$ sẽ ở vị trí $$$1 + k \times 2$$$, tuy nhiên vị trí này đã vượt quá kích thước mảng nên ta sẽ phải coi nó như vị trí $$$2$$$ rồi lại gán tiếp các vị trí $$$2 + k, ...$$$

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define int long long 

void solve(){
    int n, k; cin >> n >> k;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    int res = 0, x = n / k;
    for(int i=1; i<=n; i+=x){
        for(int j=i; j<i+x-1; j++){
            res += a[j + 1] - a[j];
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Các giá trị có thể đạt được của biểu thức $$$x$$$ $$$\%$$$ $$$y$$$ là bao nhiêu ?

Đúng, các giá trị sẽ nằm trong đoạn $$$[0, y - 1]$$$. Như vậy để có thể tối đa hoá tập hợp kết quả thì ta sẽ cần làm gì với giá trị $$$y$$$ ?

Đúng, ta sẽ chỉ cần chọn $$$y$$$ là lớn nhất có thể, như vậy $$$y = max(a_1, a_2, ..., a_n)$$$. Vậy còn giá trị $$$x$$$ thì sao ?

Đúng, ta sẽ cần chọn giá trị $$$x$$$ là giá trị lớn thứ hai trong mảng vì khi đó đáp số bài toán sẽ chính là $$$x$$$. Ngoài ra, khi mảng chỉ gồm $$$1$$$ giá trị duy nhất, đương nhiên đáp số bài toán sẽ là $$$0$$$.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

void solve(){
    int n; cin >> n;
    int a[n];
    for(int &i : a) cin >> i;
    sort(a, a + n);
    for(int i=n-1; i>0; i--){
        if(a[i] > a[i - 1]){
            cout << a[i - 1];
            return;
        }
    }
    cout << 0;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Giả dụ An sẽ làm hết $$$n \times 2$$$ công việc, vậy thì tổng thời gian giải quyết sẽ là $$$S = \sum\limits_{i = 1}^{n \times 2} a_i$$$. Như vậy, ta cần tham lam sang cho Bình $$$n$$$ công việc sao cho giảm được giá trị $$$S$$$ đi càng nhiều càng tốt.

Vì giá trị $$$S$$$ sẽ thay đổi theo hướng: đổi việc thứ $$$i$$$ từ An thành Bình $$$\to S = S - a_i + b_i = S - (a_i - b_i)$$$, nên ta sẽ cần tạo thêm một mảng lưu các giá trị $$$(a_i - b_i)$$$ và rồi chọn ra đúng $$$n$$$ giá trị lớn nhất.

#include<bits/stdc++.h>
using namespace std;

#define pe pair<int, int>
#define fi first
#define se second
int n;
pe a[1000005];
 
void solve(){
    cin >> n; n *= 2;
    int x = 0;
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
        x += a[i].fi;
    }
    sort(a+1, a+n+1, [](pe a, pe b){
        if(a.fi - a.se == b.fi - b.se) return a.se < b.se;
        return a.fi - a.se > b.fi - b.se;
    });
    for(int i=1; i*2<=n; i++){
        x = x - a[i].fi + a[i].se;
    }
    cout << x;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta dễ dàng nhận thấy rằng tập con $$$b$$$ không thoả mãn điều kiện đề bài khi và chỉ khi tồn tại $$$2$$$ số $$$x$$$ và $$$y$$$ sao cho:

$$$(x + y)$$$ $$$\%$$$ $$$k = 0$$$ $$$\to$$$ $$$((x$$$ $$$\%$$$ $$$k) + (y$$$ $$$\%$$$ $$$k))$$$ $$$\%$$$ $$$k = 0$$$.

Ta có thể rút ra $$$2$$$ nhận xét là:

• Chia dư mọi phần tử mảng cho $$$k$$$ để dễ xử lý $$$\to$$$ từ giờ coi như các số đã được chia dư cho $$$k$$$.

• Nếu $$$x = i$$$ thì $$$y = k - i$$$, như vậy ta sẽ đếm số lần xuất hiện của các số trong đoạn $$$[0, k - 1]$$$ do khi chia dư thì các kết quả chỉ nằm trong đoạn đó.

Để tập con $$$b$$$ là lớn nhất thì với mỗi cặp $$$(i, k - i)$$$ ta sẽ cần chọn ra giá trị $$$max(cnt[i], cnt[k - i])$$$. Tuy nhiên, có $$$2$$$ giá trị đặc biệt mà ta cần chú ý đó chính là $$$0$$$ và $$$k / 2$$$ (nếu $$$k$$$ là số chẵn). Lí do là bởi vì ta sẽ chỉ có thể sử dụng tối đa $$$1$$$ số $$$0$$$ duy nhất để nhét vào $$$b$$$, cũng như là tối đa $$$1$$$ số $$$k / 2$$$ (nếu $$$k$$$ là số chẵn) để nhét vào $$$b$$$.

#include<bits/stdc++.h>
using namespace std;

int cnt[1005];

void solve(){
    int n, k; cin >> n >> k;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
        ++cnt[a[i] % k];
    }
    int res = 0;
    if(cnt[0] > 0) res = 1;
    for(int i=1; i<=k/2; i++){
        if(i < k - i){
            res += max(cnt[i], cnt[k - i]);
        }else if(cnt[i] > 0) ++res;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ tách bài toán này thành $$$2$$$ bài toán con là tìm giá trị nhỏ nhất của tổng khoảng cách từ điểm $$$u$$$ đến $$$a_x$$$ và $$$v$$$ đến $$$a_y$$$.

Như vậy, ta sẽ cần biết thêm một nhận xét là trung vị của mảng sẽ là phần tử mà có tổng khoảng cách tới các phần tử trong mảng là nhỏ nhất. Dưới đây là $$$2$$$ ảnh minh hoạ:

Cụ thể hơn, khi ta dịch sang phải so với phần tử trung vị thì sẽ có $$$4$$$ phần tử tăng thêm $$$2$$$ đơn vị khoảng cách, còn chỉ có đúng $$$3$$$ phần tử giảm đi $$$2$$$ đơn vị khoảng cách. Chốt lại, ta sẽ có toạ độ điểm cần tìm là (trung vị của mảng các $$$a_x$$$, trung vị của mảng các $$$a_y$$$).

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;
    int a[n+5], b[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
    }
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    int res = 0, x = a[(n + 1) / 2], y = b[(n + 1) / 2];
    for(int i=1; i<=n; i++){
        res += abs(x - a[i]) + abs(y - b[i]);
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Với số phút $$$m$$$ có thể lên tới $$$10^9$$$, ta phải làm cách nào để xác định được hết rằng phút $$$i$$$ sẽ luyện kỹ năng nào ?

Đúng, ta không cần xét hết $$$m$$$ phút, cụ thể hơn là tối đa ta sẽ cần $$$n$$$ phút, lí do là bởi vì khi sử dụng hết lần đầu tiên của các kỹ năng thì ta sẽ chỉ luyện đúng duy nhất $$$1$$$ kỹ năng cung cấp nhiều sức mạnh nhất. Vậy thì chọn kỹ năng như nào cho phù hợp đây ?

Đúng, ta sẽ sử dụng hàng đợi ưu tiên để giải quyết bài toán này. Đầu tiên thì ta sẽ đưa vào các giá trị sức mạnh $$$e_i + s_i$$$ mà phép luyện kỹ năng có thể cung cấp, sau đó mỗi khi lấy phần tử ở đầu ra thì ta sẽ chỉ đưa lại giá trị $$$e_i$$$ vào thôi, do $$$s_i$$$ chỉ nhận được khi lần đầu luyện kỹ năng $$$i$$$ đó.

#include<bits/stdc++.h>
using namespace std;

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

#define pe pair<int, int>
#define fi first
#define se second

void solve(){
    int n, m; cin >> n >> m;
    pe a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    priority_queue<pe> q;
    for(int i=1; i<=n; i++){
        q.push({a[i].fi + a[i].se, i});
    }
    int res = 0;
    for(int i=1; i<=min(n, m); i++){
        pe top = q.top(); q.pop();
        int sc = top.fi, id = top.se;
        res += sc;
        q.push({a[id].se, id});
    }
    if(m > n) res += (m - n) * q.top().fi;
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}