Educational Codeforces Round 158 补题(A~D)

A.

思路

找出最大耗油的路程即可

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64  = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;

void solve() {
    int n, x;
    cin >> n >> x;
    std::vector<int> v(n);
    for (auto &i : v) cin >> i;

    int ans = v[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, v[i] - v[i - 1]);
    }

    if (v.back() != x) ans = max(ans, 2 * (x - v.back()));
    cout << ans << endl;

}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

B.

思路

将芯片传送才能做到后一个比前一个大

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64  = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;

void solve() {
    int n;
    cin >> n;
    std::vector<int> v(n);
    for (auto &i : v) cin >> i;
    i64 ans = 0;
    for (int i = 1; i < n; i++) {
        if (v[i] > v[i - 1]) ans += (v[i] - v[i - 1]);
    }
    cout << ans + (v[0] - 1) << endl;

}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

C.

思路

要使得数组里的所有元素相等，就要使得最大最小值相等

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64  = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;

void solve() {
    int n;
    cin >> n;
    i64 mx = -1, mn = inf;
    std::vector<i64> v(n);
    for (auto &i : v) {
        cin >> i;
        mx = max(mx, i);
        mn = min(mn, i);
    }


    vector<i64> ans;
    while (mx != mn) {
        mx = (mx + mn) / 2;
        ans.push_back(mn);
    }
    cout << ans.size() << endl;
    if (ans.size() <= n && ans.size()) {
        for(auto i : ans) cout << i << ' ';
        cout << endl;
    }

}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

D.

思路

假设最小的能杀死全部怪物的攻击力是\(x\)，第一个攻击的是\(i\)。则最坏情况下消灭第\(j\)个士兵的要满足：

• \(v[j]<=x-(n-j)\) , \(j < i\)
• \(v[j]<=x-(j-1)\) , \(j > i\)
  移项得
• \(x>=v[j]+n-j\) , \(j < i\)
• \(x>=v[j]+j-1\) , \(j > i\)

#include <bits/stdc++.h>

using namespace std;
using i64  = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;

void solve() {
    int n;
    cin >> n;
    vector<i64> v(n + 1), pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++) cin >> v[i];

    for (int i = 1; i <= n; i++) pre[i] = max(pre[i - 1], v[i] + n - i);
    for (int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], v[i] + i - 1);

    i64 ans = inf;
    for (int i = 1; i <= n; i ++) //枚举第一个攻击的是谁
        ans = min(ans, max({suf[i + 1], pre[i - 1], v[i]}));
        
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    //cin >> t;
    while (t --) solve();

    return 0;
}