A. Medium Number

三个数的中间数

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    cout << a[1] << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

B. Atilla's Favorite Problem

最大的字母是第几个字母

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n, ans = 0;
    string s;
    cin >> n >> s;
    for(auto c : s)
        ans = max(ans, c - 'a' + 1);

    cout << ans << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

C. Advantage

每个人想知道自己和除自己以外的最大值相差多少

维护一个最大值v1和一个次大值v2

遍历每个数，如果是最大值，就用自己减去次大值，否则减去最大值

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve(){
    int n;
    cin >> n;
    int v1 = 0, v2 = 0;
    for(int i = 0; i < n; i ++ )
    {
        cin >> a[i];
        if(a[i] >= v1)
        {
            v2 = v1;
            v1 = a[i];
        }
        else if(a[i] > v2)
        {
            v2 = a[i];
        }
    }
    for(int i = 0; i < n; i ++ )
    {
        if(a[i] == v1)
            cout << a[i] - v2 << " ";
        else 
            cout << a[i] - v1 << " ";
    }
    cout << "\n";
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

D. Challenging Valleys

题意就是不能有山峰，只要开始上升就不能有下降的，只要有上升的，后面只能继续上升或平行着

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve(){
    int n;
    cin >> n;
    bool f = false;
    bool ans = true;
    for(int i = 0; i < n; i ++ )
    {
        cin >> a[i];
        if(i != 0 && a[i] > a[i - 1])
            f = true;
        
        if(i != 0 && f && a[i] < a[i - 1])
            ans = false;
    }
    if(ans) puts("YES");
    else puts("NO");
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

E. Binary Inversions

题意：能对01数组进行一次操作，使一个零变成一或一变成零，求最多有多少个逆序对

我们维护一个数前面有多少个1，后面有多少个0

然后枚举使每个数改变去更新答案

如果当前点是0，要变成1：ans = max(ans, tmp - cnt1[i] + cnt0[i]);

否则：ans = max(ans, tmp + cnt1[i] - cnt0[i]);

注意：不要忘了先算一个不操作的逆序对数量

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int cnt0[N], cnt1[N];
int n;
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    int cnt = 0;
    for(int i = 1; i <= n; i ++ )    // 每个数前面有多少个1
    {
        cnt1[i] = cnt;
        if(a[i] == 1) cnt ++ ;
    }
    cnt = 0;
    for(int i = n; i >= 1; i -- )    // 每个数后面有多少个0
    {
        cnt0[i] = cnt;
        if(a[i] == 0) cnt ++ ;
    }

    long long ans = 0;
    cnt = 0;
    for(int i = n; i >= 1; i -- )    // 一次也不操作的逆序对数量
    {
        if(a[i] == 0) cnt ++ ;
        if(a[i] == 1) ans += cnt;
    }

    long long tmp = ans;
    for(int i = 1; i <= n; i ++ )    // 枚举每个改变去更新答案
    {
        if(a[i] == 0)
            ans = max(ans, tmp - cnt1[i] + cnt0[i]);
        else
            ans = max(ans, tmp + cnt1[i] - cnt0[i]);
    }
    cout << ans << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

F. Quests

先判断 Infinity 和 Impossible 两种情况

如果数组中最大值天天拿也够不到，maxv * d < c ，puts("Impossible");

如果数组中最大值就大于等于c， maxv >= c， puts("Infinity");

除此之外，就二分天数，找满足条件最大的k、

​ 条件：周期为k + 1，

​ 查看有几个周期 d / (k + 1)，

​ 剩下的在加上，大于等于c就true，否则就false

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n, d;
long long c;

bool check(int k)
{
    k += 1;
    int day = min(k, n);
    long long tmp = 0;
    for (int i = 1; i <= day; i++)
        tmp += a[i];

    long long res = (long long)d / (k) * tmp;
    if (res >= c)
        return true;
    
    for (int i = 1; i <= min(n, d % (k)); i++)
    {
        res += a[i];
        if (res >= c)
            return true;
    }
    return false;
}

void solve()
{
    cin >> n >> c >> d;

    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1, greater<int>());

    int maxv = a[1];
    if ((long long)maxv * d < c)
    {
        puts("Impossible");
        return;
    }
    if (maxv >= c)
    {
        puts("Infinity");
        return;
    }

    int l = 0, r = d;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (!check(mid))
            r = mid - 1;
        else
            l = mid;
    }
    cout << l << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while (_t--)
    {
        solve();
    }
    return 0;
}