Educational Codeforces Round 3

https://codeforces.com/contest/609
3/6：ABC
D赛后过了
CD题解等下写

A. USB Flash Drives

前缀和

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int n, a[N];

int main () {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)        cin >> a[i];
    sort (a + 1, a + n + 1, greater<int>());
    for (int i = 1; i <= n; i++) {
        m -= a[i];
        if (m <= 0) {
            cout << i;
            break;
        }
    }
}

B. The Best Gift

容斥思想？
任意 \(n\) 个数中选两个的方案数是 \(C_{n}^{2}\)
其中除去各相同的方案数就是答案。

#include <bits/stdc++.h>
#define int long long

using namespace std;
int a[15];

signed main () {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a[x] ++;
    }
    int ans = n * (n - 1) / 2;
    for (int i = 1; i <= m; i++) {
        ans -= a[i] * (a[i] - 1) / 2;
    }
    cout << ans;
}

C. Load Balancing

小思维，考虑到总和是不变的。所以最终所有数字的局面是固定的，那么只需排序之后计算差值即可。
最终局面就是：

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5;
int a[N], sum, ans, n;

signed main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], sum += a[i];
    sort (a + 1, a + n + 1);
    //cout << sum << endl;
    int val = sum / n, cnt = sum - val * n;
    //cout << val << ' ' << cnt << endl; //有n - cnt个val, cnt个val + 1
    for (int i = 1; i <= n - cnt; i++) {
        ans += abs (a[i] - val);
    }
    for (int i = n - cnt + 1; i <= n; i++) {
        ans += abs (a[i] - (val + 1));
    }
    cout << ans / 2 << endl;
}

D. Gadgets for dollars and pounds

二分。

// LUOGU_RID: 97555092
#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, inf = 1e9;
int n, m, k, s;
pair<ll, int> a[N], b[N];
int ss[3], id[3];
pii result[N];

struct Node {
    int id, type;
    ll cost;
}p[N];

bool cmp (Node p1, Node p2) {
    ll sum1 = 0, sum2 = 0;
    return 1ll * ss[p1.type] * p1.cost < 1ll * ss[p2.type] * p2.cost;
}

bool check (int mid) {
    id[1] = a[mid].second, id[2] = b[mid].second;
    ss[1] = a[mid].first, ss[2] = b[mid].first;
    sort (p + 1, p + m + 1, cmp);
    //for (int i = 1; i <= m; i++)    cout << ss[p[i].type] * p[i].cost << ' ';
    //cout << endl;
    ll sum = 0;
    for (int i = 1; i <= k; i++) {
        sum += 1ll * ss[p[i].type] * p[i].cost;
        //cout << sum << ' ';
        if (sum > s)    return false;
    }
    for (int i = 1; i <= k; i++) {
        result[i].first = p[i].id;
        result[i].second = id[p[i].type];
    }
    return true;
}

signed main () {
    cin >> n >> m >> k >> s;
    ll mina = 1e9, minb = 1e9;
    int id1, id2;
    for (int i = 1; i <= n; i++) {
        ll x;   cin >> x;
        if (x < mina)   mina = x, id1 = i;
        a[i] = {mina, id1};
    }
    for (int i = 1; i <= n; i++) {
        ll x;   cin >> x;
        if (x < minb)   minb = x, id2 = i;
        b[i] = {minb, id2};
    }

    for (int i = 1; i <= m; i++) {
        int x;
        ll y;
        cin >> x >> y;
        p[i] = {i, x, y};
    }
   
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check (mid)) {
            ans = mid, r = mid - 1;
        }
        else    l = mid + 1;
        //cout << l << ' ' << r << endl;
    }
    if (ans == -1)     cout << "-1\n";
    else {
        cout << ans << endl;
        for (int i = 1; i <= k; i++)  cout << result[i].first << ' ' << result[i].second << endl;
    }
}


//n天,m物品,买k个,现有s元
//两种货币a,b
//给出n天对应的汇率以及所有物品的两种价格
//最快能在第几天把k件物品买完,在哪天买的第几种物品
//一种商品只能购买一次，但是一天可以买多种商品。
//钱是可以一次性转换的

E. Minimum spanning tree for each edge

F. Frogs and mosquitoes