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

【C++贪心】P9344 去年天气旧亭台|普及

news 2025/5/10 4:50:44

本文涉及知识点

C++贪心

去年天气旧亭台

题目背景

依旧是过往的天气，过往的楼台烟雨。时间悄悄流逝着，山河仍在，人却已不是过去的人……

题目描述

登上楼台，旧时满面沉灰的地板映入眼帘。

共有 $n$ 块地板，地板分为两类，第 $i$ 块地板的类别用 $c_i$ 表示，积灰程度用 $a_i$ 表示。注意 $c_i$ 为 $0$ 或 $1$ 。

现在要清理这些地板上的灰尘。每次操作中，你可以：

选择两个下标 $i, j$ ，满足 $1\leq i\leq j\leq n$ ， $c_i=c_j$ ，且第 $i$ 块和第 $j$ 块地板上的灰尘均未被清理过；
花费 $a_i+a_j$ 的能量清理第 $i$ 块到第 $j$ 块所有地板上的灰尘。

求清理完所有地板上的灰尘至少要多少能量。

输入格式

本题有多组测试数据。

第一行一个整数 $T$ ，表示测试数据组数。

对于每组测试数据：

第一行一个整数 $n$ 。
第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$ 。
第三行 $n$ 个整数 $c_1,c_2,\dots,c_n$ 。

输出格式

对于每组测试数据，一行一个整数表示最小能量。

样例 #1

样例输入 #1

2
6
1 1 4 5 1 4
1 0 0 1 0 1
8
3 1 4 1 5 9 2 6
1 0 1 0 1 0 1 0

样例输出 #1

5
13

提示

【样例 1 解释】

对于第一组数据，直接花费 $a_1+a_6=5$ 的能量清理所有灰尘。
对于第二组数据，先花费 $a_1+a_1=6$ 的能量清理第一个地板上的灰尘，再花费 $a_2+a_8=7$ 的能量清理剩余灰尘。

【数据规模与约定】

对于 $10\%$ 的数据，保证 $T\le 10$ ， $n\le 10$ ；

对于 $40\%$ 的数据，保证 $T\le 20$ ， $n\le 10^3$ ；

另有 $10\%$ 的数据，保证 $c_i=1$ ；

对于 $100\%$ 的数据，保证 $\le T \le 10^5$ ， $\le n,\sum n\le 2 \times 10^6$ ， $c_i \in \{0,1\}$ ， $\le a_i \le 10^9$ 。

贪心

我们把每次的操作的i,j，看做一个以i和j为端点的线段。
性质一：两条线段不会包含，否则取消被包含的线段。操作成本更小。
性质二：两条线段不会交叉，否则后面操作的i或j，已经清理。
性质三：所有地板都要清理，故所有线段都相邻。
性质四：1和N必定是线段的顶端。
推论一：如果1和N的类型相同，则直接[1,N]，成本最小。
如果1和N类型不同，至少两条线段：且第一线段[1,i1]，第二条线段以i1+1为起点。即至少包括4个端点1,i,i+1,N。[i1+1,N]便是最优解。
i1和必须和1的类型同，i1+1必须和N的类型同。
枚举i1,i1 $\in$ [1,N-1]

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>#include <bitset>
using namespace std;template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {vector<T> ret;T d ;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}template<class T = int>
vector<T> Read( const char* pFormat = "%d") {int n;scanf("%d", &n);vector<T> ret;T d;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}string ReadChar(int n) {string str;char ch;while (n--) {do{scanf("%c", &ch);} while (('\n' == ch));str += ch;}return str;
}class Solution {
public:long long MaxS(vector<int> a,vector<int> c) {const int N = a.size();long long ans = a.front() + a.back();int other = INT_MAX;if (c.front() == c.back()) { return ans ; }for (int i = 0; i + 1 < N; i++) {if ((c[i] == c[0]) && (c[i + 1] == c.back())) {other = min(other, a[i] + a[i + 1]);}}return ans + other;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint T;scanf("%d", &T);while (T--) {int n;scanf("%d", &n);auto a = Read<int>(n);auto c = Read<int>(n);auto res = Solution().MaxS(a, c);cout << res << std::endl;}	return 0;
}

单元测试

	vector<int> a, c;TEST_METHOD(TestMethod11){a = { 1,1,4,5,1,4 }, c = { 1,0,0,1,0,1 };auto res = Solution().MaxS(a, c);AssertEx(5ll, res);}TEST_METHOD(TestMethod12){a = { 3,1,4,1,5,9,2,6 }, c = { 1,0,1,0,1,0,1,0 };auto res = Solution().MaxS(a, c);AssertEx(13ll, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功