CF ABBYY Cup 3.0 - Finals A2. Oh Sweet Beaverette 题解 前缀和 贪心

本文主要是介绍CF ABBYY Cup 3.0 - Finals A2. Oh Sweet Beaverette 题解 前缀和 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Oh Sweet Beaverette

题目描述

有一个森林共有 $n$ 棵树，它们各自都有美丽值，要砍掉一些树，也可以不砍。
要求：

1. 剩余树的美丽值之和必须最大化；
2. 结果中第一棵和最后一棵树的美丽值必须相同；
3. 森林中必须至少剩下两棵树。

问：需要砍下哪些树才能让剩余树的美丽值之和最大化？

输入格式

第一行包含一个整数 $n$，表示森林中树的数量。
第二行包含 $n$ 个整数 $a_i$，表示每棵树的美丽值。所有树的美丽值的绝对值都不超过 $10^9$。

输出格式

第一行输出两个整数，分别表示剩余树的美丽值之和与砍掉的树木数量 $k$。
接下来一行输出 $k$ 个整数，为砍掉的树的编号。假设从左到右树的编号是 $1$~$n$。

如果有多种解决方案，请打印其中任何一个。保证至少有两棵树的美丽值相同。

样例 #1

样例输入 #1

5
1 2 3 1 2

样例输出 #1

8 1
1

样例 #2

样例输入 #2

5
1 -2 3 1 -2

样例输出 #2

5 2
2 5

原题

Codeforces——传送门
洛谷——传送门

代码

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;vector<ll> a(n + 1); // 美观度数组for (int i = 1; i <= n; i++){cin >> a[i];}unordered_map<int, int> first; // 记录某个美观度第一次出现的位置unordered_map<int, int> last;  // 记录某个美观度最后一次出现的位置vector<ll> sum(n + 1, 0);      // 美观度前缀和for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] + max(a[i], 1ll * 0); // 若美观度为负数，就砍伐，不记录其中if (first.count(a[i]) == 0)first[a[i]] = i; // 只有当第一次出现时才赋值last[a[i]] = i;      // 不断更新最后一次出现的位置}int l, r;                                                                           // 记录美观度总和最大时的首尾位置ll ans = LLONG_MIN;                                                                 // 初始化为最小值for (unordered_map<int, int>::iterator it = first.begin(); it != first.end(); it++) // 遍历所有美观度相同的距离最长的树对{int left = it->second;int right = last[it->first];if (left == right)continue; // 该美观度不存在于两棵及以上的树，跳过// cur记录当前美观度总和。由于sum记录的是所有大于0的美观度的前缀和，而首尾的树不能砍掉，所有首尾的美观度计算时应单独加上a[right]和a[left]ll cur = sum[right - 1] - sum[left] + a[right] + a[left];if (cur > ans){ans = cur;l = left;r = right;}}int cnt = 0;     // 需砍伐的树木数量vector<int> pos; // 需砍伐的树木位置for (int i = 1; i <= n; i++){if (i < l || i > r) // 在区间[l,r]之外，需要砍伐{cnt++;pos.push_back(i);}else if (i > l && i < r){if (a[i] < 0) // 在区间(l,r)中，如果美观度小于0，则需要砍伐{cnt++;pos.push_back(i);}}}// 输出结果cout << ans << ' ' << cnt << '\n';for (int i = 0; i < pos.size(); i++){if (i != pos.size() - 1)cout << pos[i] << ' ';elsecout << pos[i] << '\n';}return 0;
}

这篇关于CF ABBYY Cup 3.0 - Finals A2. Oh Sweet Beaverette 题解 前缀和 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---