Educational Codeforces Round 106 (Rated for Div. 2) C

作者：代码大牛 | 2024-02-02 11:29:36

踩

educational codeforces round 106 (rated for div. 2)

还是太菜了，17分钟签完到，就自闭了。
在这里插入图片描述

C题

题目描述
你从 $(0, 0)$ 走到 $(n, n)$ ，只能 $u p / r i g h t$ ，每次方向转变，最多只能转变 $(n - 1)$ 次，所以就有n个 $s e g m e n t$ 。然后还会给你 $n^~$ 个cost- $C_i$ 。问你最小花费是多少。
思路
当时比赛的时候就想到是贪心，就是最小的那个走多点，其他的只走1步。但是没想到奇偶分开考虑，然后用个奇偶前缀和，动态维护最小值。神奇呀！！！
代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
ll c[N];
#define PII pair<int,int>
#define x first
#define y second
#define PB push_back
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	ll mino=c[1],mine=c[2];//奇偶的最小值
	ll cnto=1,cnte=1;//这个最小值前面的数量
	ll qiano=c[1],qiane=c[2];//奇偶前缀和
	ll ans=n*c[1]+n*c[2];
	for(int i=3;i<=n;i++){
		if(i&1){
			mino=min(mino,c[i]);
			ans=min(ans,qiano+qiane+(n-cnto)*mino+(n-cnte)*mine);
			cnto++;qiano+=c[i];
		}
		else{
			mine=min(mine,c[i]);
			ans=min(ans,qiano+qiane+(n-cnto)*mino+(n-cnte)*mine);
			cnte++;qiane+=c[i];
		}
		//cout<<i<<" "<<ans<<endl;
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/55084