Znzryb's Blog
0%

2026C. Action Figures

Posted on Edited on

思路讲解

总体思路就是一个贪心，想办法省最多的钱。首先，这一天他没有去，那这钱他是省不了了，因为后面的天他去，肯定省后面的多的钱，前面的天也没法买他，因此，我们把这个人加到que0里（实际是一个栈，这种我应该用deque，代码里是vector）。

然后可以省钱的，必须要给他找个搭档，先在que0里找，再在rem（A[i]==’1’的i的set）里找，找小的（通过删除rem.begin()实现）。

AC代码

https://codeforces.com/contest/2026/submission/309701489

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Problem: C. Action Figures
// Contest: Codeforces - Educational Codeforces Round 171 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/2026/C
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(4e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
char A[MAXN];

inline void solve(){
	cin>>N;
	ll ans=(1+N)*N/2;
	vector<ll> seq0;
	set<ll> rem;
	for(int i=1;i<=N;++i){
		cin>>A[i];
		if(A[i]=='0') seq0.push_back(i);
		if(A[i]=='1') rem.insert(i);
	}
	ll idx=0;
	// for(int i=N;i>=1;--i){
		// if(i<=idx) break;
		// if(A[i]=='1' && vis[i]){
// 			
			// ans-=i;
			// ++idx;
		// }
	// }
// #ifdef LOCAL
    // cerr << "OK "<<T << '\n';
// #endif
	while(!rem.empty()){
		set<ll>::iterator it=prev(rem.end());
		while(!seq0.empty() && seq0.back()>*it ){
			seq0.pop_back();
		}
// #ifdef LOCAL
    // cerr << seq0.back() << '\n';
// #endif
		if(!seq0.empty()){
			seq0.pop_back();
			ans-=*it;
		}else{
			if(rem.size()>=2){
				rem.erase(rem.begin());
				ans-=*it;
// #ifdef LOCAL
    // cerr << ans <<" "<< *it << '\n';
// #endif
			}
		}
		rem.erase(it);
	}
	cout<<ans<<"\n";

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();

	}
	return 0;
}
/*
AC
https://codeforces.com/contest/2026/submission/309701489
*/

心路历程（WA，TLE，MLE……）