Codeforces Round 931 (Div. 2)

在这里插入图片描述

Codeforces Round 931 (Div. 2)

A. Too Min Too Max

题意：

从n个元素中选取四个元素进行按任意顺序排列，进行以下计算，求出可能的最大值

$a_i - a_j| + |a_j - a_k| + |a_k - a_l| + |a_l - a_i|$

思路：

排序，取两对头尾元素，大小元素交叉排列，别忘了头尾元素。

AC code：

void solve() {
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int l = 0, r = n - 1;
    vector<int> b;
    b.pb(a[l]);
    b.pb(a[r]);
    l ++, r --;
    b.pb(a[l]);
    b.pb(a[r]);
    int ans = 0;
    for (int i = 1; i < 4; i ++) {
       ans += abs(b[i] - b[i - 1]);
    }
    ans += abs(b[0] - b[3]);
    cout << ans << endl;
}

B. Yet Another Coin Problem

题意：

有五种不同面值的硬币{1, 3, 6, 10, 15}，选取任意数量的硬币使得它们的总价值为n，最少选取多少硬币。

思路：

分别找出n为1到15时需要的最少硬币，然后枚举用五种面额的硬币去计算时的需要多少个，剩下的需要补多少；

特殊的是，可能会出现用面额为15的硬币，余数为8，此时额外需要3枚硬币，但如果少用一枚15硬币，那么23的价值可以用10+10+3来替代，少用一枚硬币，类似这种情况就先减去当前枚举的面额，再枚举一次五种面额的硬币是否可能用更少的可能去替代。

描述稀碎，详见代码。

AC code：

void solve() {
    cin >> n;
    int f[5] = {1, 3, 6, 10, 15};
    int cnt[16] = {0, 1, 2, 1, 2, 3, 1, 2, 3, 2, 1, 2, 2, 2, 3, 1};
    int ans = n, now = 0;
    for (int i = 0; i < 5; i ++) {
        now = n / f[i] + cnt[n % f[i]];
        ans = min(ans, now);
        now = n / f[i] - 1;
        if (now >= 0) {
            int ca =  n % f[i] + f[i], now1 = n;
            for (int i = 0; i < 5; i ++) {
                now1 = min(now1, ca / f[i] + cnt[ca % f[i]]);
            }
            now += now1;
            ans = min(now, ans);
        }
    }
    cout << ans << endl;
}

C. Find a Mine

题意：

怎么天天交互起来了，没白玩扫雷。。。

扫雷游戏，在n*m的格子内找出两枚雷中的一个，最多四次询问，每次可以询问任意坐标到两枚雷中较小的曼哈顿距离，即：

$min(|x-x _ 1|+|y-y _ 1|, |x-x _ 2|+|y-y _ 2|)$ 。

思路：

首先从样例可以看出一点，询问四个角的元素可以最大限度的缩小一颗雷的范围，因为相同的距离的坐标都在一条对角线上；
假设我们第一次询问坐上角(1, 1)的元素，那么可以得到至少一颗雷所在的对角线，通过第一次询问到的距离d，还可以直接求出对角线两端的坐标，分别为(1 +d , 1)和(1, d + 1)，注意，图不是一个正方形(吃亏了一发)，可能会出现1+d大于当前边界的，此时将大于边界的横/纵坐标改为边界点，多出的距离加到另一个横/纵坐标上即可；
然后接下来两次询问分别为对角线两端的距离询问，因为至少有一颗雷一定在该对角线上，两次询问求出的两个d1和d2一定有一个是靠近相应对角线边界点的曼哈顿距离；
那么最后一次询问挑其中一个对角线边界点求出可能的雷点坐标进行询问，若是雷，直接输出，否则另一个点对应的雷点即为答案
注意四次询问期间若出现d=0，则说明当前点为雷点，直接输出即可。

AC code：

void solve() {
    cin >> n >> m;
    cout << '?' << ' '  << 1 << ' ' << 1 << endl;
    int d; cin >> d;
    if (d == 0) {
        cout << '!' << ' ' << 1 << ' ' << 1 << endl;
        return;
    }
    int lx = d + 1, ly = 1; //对角线左下
    int rx = 1, ry = d + 1; //右上
    if (lx > n) {
        ly += (lx - n);
        lx = n;
    }
    if (ry > m) {
        rx += (ry - m);
        ry = m;
    }
    cout << '?' << ' ' << lx << ' ' << ly << endl;
    cin >> d;
    if (d == 0) {
        cout << '!' << ' ' << lx << ' ' << ly << endl;
        return;
    }
    int mayl = d;
    cout << '?' << ' ' << rx << ' ' << ry << endl;
    cin >> d;
    if (d == 0) {
        cout << '!' << ' ' << rx << ' ' << ry << endl;
        return;
    }
    int mayr = d;
    cout << '?'<< ' '  << lx - mayl / 2 << " " << ly + mayl / 2 << endl;
    cin >> d;
    if (d == 0) {
        cout << '!' << ' ' << lx - mayl / 2 << " " << ly + mayl / 2 << endl;
        return;
    } else {
        cout << '!' << ' ' << rx + mayr / 2 << " " << ry - mayr / 2 << endl;
    }
}

秒客网

Codeforces Round 931 (Div. 2)