题目：去年天气旧亭台
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P9344
- 标签：
贪心 - 难度：普及/提高-
题解
思路
- 两个可能性
- 第一块瓷砖和最后一块是同类型，此时最小开支必为第一块费用 最后一块费用，因为中间的开支均为无效
- 第一块和最后一块不是同类型，此时选择两块类型不同的位于中间的瓷砖
- 因为第一块和最后一块必定需要支出费用，所以中间部分能省则省
- 此时需要注意中间部分选中的两块瓷砖必定是紧连着的，否则两块瓷砖中间的部分也有额外开支
- 然后两块瓷砖类型顺序不能反！！！
- 例如首块是0，中间选中的两块类型为1的更靠左，中间就会有重叠部分
- 不开long long见祖宗！！
代码：20分
- 纯暴力打发，卡掉一部分数据，收得20分
#include <bits/stdc .h>
using namespace std;
#define endl 'n';
struct edge {
int v, k;
};
void best_coder() {
int t;
cin >> t;
while(t > 0) {
--t;
int n;
cin >> n;
int l, r;
cin >> l;
for (int i = 1; i < n - 1; i) {
int a;
cin >> a;
}
cin >> r;
for (int i = 0; i < n; i) {
int a;
cin >> a;
}
cout << l r << endl;
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
void best_coder() {
int t;
cin >> t;
while(t > 0) {
--t;
int n;
cin >> n;
vector<long long> v(n);
vector<long long> k(n);
for (int i = 0; i < n; i) {
cin >> v[i];
}
for (int i = 0; i < n; i) {
cin >> k[i];
}
if (n == 1) {
cout << v[0] << endl;
continue;
}
if (k[0] == k[n - 1]) {
cout << v[0] v[n - 1] << endl;
} else {
long long ans = 0x7f7f7f7f7f7f7f7f;
for (int i = 1; i < n - 1; i) {
if (k[i] == k[0] && k[i 1] == k[n - 1]) {
ans = min(ans, v[i] v[i 1]);
}
}
for (int i = 1; i < n - 1; i) {
if (k[i] == k[n - 1] && k[i - 1] == k[0]) {
ans = min(ans, v[i] v[i - 1]);
}
}
cout << ans v[0] v[n - 1] << endl;
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
