当前位置：首页 > article >正文

Codeforces Round 975 (Div. 2) A. Max Plus Size

article 2024/9/28 17:05:58

题目链接：题目

大意：

可以给一些数字涂为红色，但是红色不能相邻，设得分为被标为红色的最大数字，加上红色数字的数量，求最大得分。

思路：

先考虑最大化红色数字的数量，也就是隔一个涂一个，如果是偶数个数字，那么就是 $n /2$ ，奇数就是 $n /2$ 或 $n /2 + 1$ 。然后考虑最大红色数字，在偶数的情况下，我们一定能选到数组中的最大值，然后再加上 $n /2$ ；然而在奇数的情况下，取到最大值时不一定能取到最大的 $n /2 + 1$ ，这取决于最大值的位置。
第一次提交wa了，因为最大值可能存在于多个位置，而我只找了第一个，应该把所有最大值找出来，看有没有下标为偶数的。

代码：

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

#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define vec vector

void solve(){
    int n;
    cin >> n;
    vec<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    if(n % 2 == 0)
        cout << *max_element(a.begin(), a.end()) + n / 2 + (n % 2 != 0) << '\n';
    else{
        int mx = a[0];
        for(int i = 0; i < n; i++){
            mx = max(mx, a[i]);
        }
        bool flag = 0;
        for(int i = 0; i < n; i++){
            if(mx == a[i] && i % 2 == 0){
                flag = 1;
            }
        }
        if(flag){
            cout << mx + n / 2 + 1 << '\n';
        }else{
            cout << mx + n / 2 << '\n';
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}