CF1991A Maximize the Last Element

原题链接：A. Maximize the Last Element

Tag：观察

题目描述

给定一个长度为 \(n\) 的数组 \(a\)， 其中 \(n\) 是奇数。

在一次操作中可以同时删除任意两个相邻的数字， 需要重复这个操作直到数组只剩下一个数字， 问最后剩下的数字最大是多少？

分析

首先我们造几组样例手玩一下， 比如有一个 \(\{1,2,3\}\)， 我们可以删除其中的 \(1、2\) 或者 \(2、3\) 这样一来剩下的数字只可能是 \(1\) 或者 \(3\)。

再尝试一下 \(\{1,2,3,4,5\}\)， 我们会发现可能剩下的数字是 \(1,3,5\)， 可以发现剩下的数字只可能是位于奇数位置的数字， 于是我们只需要找出所有奇数位置中最大的数字就可以了。

以上的观察可以这样来理解： 我们每次删除相邻的数字， 可以理解为删除了一个位于偶数位的数字和一个奇数位的数字， 因为题目给出的数组大小一定是奇数， 所以奇数位的数字永远比偶数位的数字多一个， 因此删除到最后一定会剩下一个位于奇数位的数字。

代码实现

void NeverSayNever() {
    int n;
    cin >> n;
    vector<int> vec(n);
    for (auto &x: vec) cin >> x;
    int mx = INT_MIN;
    for (int i = 0; i < n; i += 2) {
        mx = max(mx, vec[i]);
    }
    cout << mx << endl;
}

额外思考

笑点解析：我赛时开局挂了一发。

日志

本页面创建于 2024/7/29 21:50