思维,CF1990 C - Mad MAD Sum
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
C - Mad MAD Sum |
二、解题报告
1、思路分析
我们考虑第一波操作后数组长什么样?
若干个数字块,且呈升序
注意到第一次操作后会有个别的长度为1的数字块
我们发现从第二次操作开始,每个长度 >= 2的数字块都会向右滑动一位
而第一次操作出现的长度为1的数字块都会被覆盖掉
也就是说,两次操作后就是整个数组向右不断移动的过程
然后问题就解决了qwq
2、复杂度
时间复杂度: O(N)空间复杂度:O(N)
3、代码详解
#include <bits/stdc++.h>
#define sc scanf
using i64 = long long;
constexpr double eps = 1e-12;
const int inf = 1e9 + 7, P = 114584;
void solve() {
int n;
std::cin >> n;
std::vector<i64> a(n);
for(int i = 0; i < n; ++ i)
std::cin >> a[i];
i64 res = 0;
for(int i = 0; i < 2; ++ i) {
std::vector<bool> vis(n + 1);
i64 ma = 0;
for(i64& x : a) {
if(vis[x])
ma = std::max(ma, x);
vis[x] = true;
res += x;
x = ma;
}
}
for (int i = 0; i < n; ++ i)
res += (n - i) * a[i];
std::cout << res << '\n';
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int _ = 1;
std::cin >> _;
while (_ --)
solve();
return 0;
}
原文地址:https://blog.csdn.net/EQUINOX1/article/details/140580776
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!