admin管理员组文章数量:1567248
A. Wallet Exchange
时间限制: 1秒
内存限制: 256兆
输入: 标准输入
输出: 标准输出
Alice and Bob are bored, so they decide to play a game with their wallets. Alice has a
coins in her wallet, while Bob has b
coins in his wallet.
Both players take turns playing, with Alice making the first move. In each turn, the player will perform the following steps in order:
- Choose to exchange wallets with their opponent, or to keep their current wallets.
- Remove 1 coin from the player’s current wallet. The current wallet cannot have 0 coins before performing this step.
The player who cannot make a valid move on their turn loses. If both Alice and Bob play optimally, determine who will win the game.
爱丽丝和鲍勃很无聊,于是他们决定用自己的钱包玩一个游戏。爱丽丝的钱包里有 a a a 枚硬币,而鲍勃的钱包里有 b b b 枚硬币。
双方轮流玩,由爱丽丝先走棋。在每个回合中,玩家将按顺序执行以下步骤:
- 选择与对手交换钱包,或保留现有钱包。
- 从玩家当前钱包中取出 1 1 1 个硬币。在执行此步骤之前,当前钱包中不能有 0 0 0 枚硬币。
无法在自己的回合中做出有效举动的玩家输。如果爱丽丝和鲍勃都以最佳方式下棋,则决定谁将赢得游戏。
输入
每个测试包含多个测试用例。第一行包含一个整数 t t t ( 1 ≤ t ≤ 1000 1 \leq t \leq 1000 1≤t≤1000 ) - 测试用例的数量。测试用例说明如下。
每个测试用例的第一行也是唯一一行包含两个整数 a a a 和 b b b ( 1 ≤ a , b ≤ 1 0 9 1 \leq a, b \leq 10^9 1≤a,b≤109 )–分别是爱丽丝和鲍勃钱包中的硬币数量。
输出
对于每个测试案例,如果 Alice 将赢得游戏,则输出 “Alice”;如果 Bob 将赢得游戏,则输出 “Bob”。
示例
输入
10
1 1
1 4
5 3
4 5
11 9
83 91
1032 9307
839204 7281
1000000000 1000000000
53110 2024
输出
Bob
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
注意
在第一个测试案例中,游戏示例如下:
- 爱丽丝在第一步中选择不与鲍勃交换钱包。现在, a = 0 a=0 a=0 和 b = 1 b=1 b=1。
- 由于爱丽丝的钱包是空的,所以鲍勃必须选择在第 1 步中不交换钱包。现在是 a = 0 a=0 a=0 和 b = 0 b=0 b=0。
- 由于爱丽丝和鲍勃的钱包都是空的,爱丽丝无法下一步棋。因此,鲍勃获胜。
在第二个测试案例中,棋局示例如下:
- 爱丽丝在第一步中选择与鲍勃交换钱包。现在, a = 3 a=3 a=3 和 b = 1 b=1 b=1。
- 鲍勃选择在第一步中与爱丽丝交换钱包。现在, a = 1 a=1 a=1 和 b = 2 b=2 b=2。
- 爱丽丝选择在第 1 步不与鲍勃交换钱包。现在是 a = 0 a=0 a=0 和 b = 2 b=2 b=2。
- 由于爱丽丝的钱包是空的,鲍勃只能选择在第 1 步不与爱丽丝交换钱包。现在, a = 0 a=0 a=0 和 b = 1 b=1 b=1。
- 由于爱丽丝的钱包是空的,爱丽丝只能选择在第 1 步中与鲍勃交换钱包。现在是 a = 0 a=0 a=0 和 b = 0 b=0 b=0。
- 由于爱丽丝的钱包和鲍勃的钱包都是空的,鲍勃无法下一步棋。因此,爱丽丝获胜。
解题思路
仔细观察不难发现,每次行动,除非钱包都为 0 0 0,否则一定可以使一个钱包里的硬币 − 1 -1 −1,到自己行动时,钱包都为 0 0 0,则输了。
那么只要计算两个钱包的硬币之和,然后判断一下奇偶性,钱包都为 0 0 0时会传到谁手里谁就行了。
题解
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>
#define endl '\n'
#define ft first
#define sd second
#define yes std::cout<<"Yes\n";
#define no std::cout<<"No\n";
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef queue <int> qi;
typedef queue <ll> ql;
typedef queue <pii> qpii;
typedef queue <pll> qpll;
typedef queue <psi> qpsi;
typedef queue <psl> qpsl;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpl;
typedef priority_queue<psi> pqpsl;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<string, int> msi;
typedef map<string, ll> msl;
typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;
void cinv(vi vec,int n) {for (int i = 1; i <= (n); i++)cin >> (vec)[i];}
void rcinv(vi vec, int n) {for (int i = (n); i >= 1; i--)cin >> (vec)[i];}
void coutv(vi vec, int n) { for (int i = 1; i <= (n); i++)cout << (vec)[i] << " "; cout << '\n'; }
void rcoutv(vi vec, int n) { for (int i = (n); i >= 1; i--)cout << (vec)[i] << " "; cout << '\n'; }
void solve()
{
ll a,b;
cin>>a>>b;
if((a+b)%2)
cout<<"Alice"<<endl;
else
cout<<"Bob"<<endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B. Plus-Minus Split
时间限制: 1秒
内存限制: 256兆
输入: 标准输入
输出: 标准输出
You are given a string s s s of length n n n consisting of characters “+” and “-”. s s s represents an array a a a of length n n n defined by a i = 1 a_i = 1 ai=1 if s i s_i si = “+” and a i = − 1 a_i = -1 ai=−1 if s i s_i si = “-”.
You will do the following process to calculate your penalty:
- Split a a a into non-empty arrays b 1 , b 2 , . . . , b k b_1, b_2, ..., b_k b1,b2,...,bk such that b 1 + b 2 + . . . + b k = a b_1 + b_2 + ... + b_k = a b1+b2+...+bk=a, where “+” denotes array concatenation.
- The penalty of a single array is the absolute value of its sum multiplied by its length. In other words, for some array c c c of length m m m, its penalty is calculated as p ( c ) = ∣ c 1 + c 2 + . . . + c m ∣ ⋅ m p(c) = |c_1 + c_2 + ... + c_m| \cdot m p(c)=∣c1+c2+...+cm∣⋅m.
- The total penalty that you will receive is p ( b 1 ) + p ( b 2 ) + . . . + p ( b k ) p(b_1) + p(b_2) + ... + p(b_k) p(b1)+p(b2)+...+p(bk).
If you perform the above process optimally, find the minimum possible penalty you will receive.
给定长度为 n n n 的字符串 s s s 由字符 “+“和”-“组成。 s s s表示长度为 n n n的数组 a a a ,如果 s i s_i si 为 “+”,则由 s i = 1 s_i=1 si=1 ;如果 s i s_i si 为”-”,则由 s i = − 1 s_i=-1 si=−1 。
您将按以下步骤计算罚金:
- 将 a a a 分割成非空数组 b 1 , b 2 , … , b k b_1,b_2,\ldots,b_k b1,b2,…,bk ,从而得到 b 1 + b 2 + … + b k = a † b_1+b_2+\ldots+b_k=a^\dagger b1+b2+…+bk=a† ,其中 + + + 表示数组连接。
- 单个数组的惩罚值是其和的绝对值乘以长度。换句话说,对于长度为 m m m 的数组 c c c ,其惩罚计算结果为 p ( c ) = ∣ c 1 + c 2 + … + c m ∣ ⋅ m p(c)=|c_1+c_2+\ldots+c_m| \cdot m p(c)=∣c1+c2+…+cm∣⋅m 。
- 你将收到的罚金总额为 p ( b 1 ) + p ( b 2 ) + … + p ( b k ) p(b_1)+p(b_2)+\ldots+p(b_k) p(b1)+p(b2)+…+p(bk) 。
如果以最优方式执行上述过程,请找出你将收到的最小惩罚。
† ^\dagger † 将 a = [ 3 , 1 , 4 , 1 , 5 ] a=[3,1,4,1,5] a=[3,1,4,1,5] 分割成 ( b 1 , b 2 , … , b k ) (b_1,b_2,\ldots,b_k) (b1,b2,…,bk) 的有效方法有 ( [ 3 ] , [ 1 ] , [ 4 ] , [ 1 ] , [ 5 ] ) ([3],[1],[4],[1],[5]) ([3],[1],[4],[1],[5]) 、 ( [ 3 , 1 ] , [ 4 , 1 , 5 ] ) ([3,1],[4,1,5]) ([3,1],[4,1,5]) 和 ( [ 3 , 1 , 4 , 1 , 5 ] ) ([3,1,4,1,5]) ([3,1,4,1,5]) ,而将 a a a 分割成无效方法有 ( [ 3 , 1 ] , [ 1 , 5 ] ) ([3,1],[1,5]) ([3,1],[1,5]) 、 ( [ 3 ] , [ ] , [ 1 , 4 ] , [ 1 , 5 ] ) ([3],[],[1,4],[1,5]) ([3],[],[1,4],[1,5]) 和 ( [ 3 , 4 ] , [ 5 , 1 , 1 ] ) ([3,4],[5,1,1]) ([3,4],[5,1,1]) 。
输入
每个测试包含多个测试用例。第一行包含一个整数 t t t ( 1 ≤ t ≤ 1000 1 \leq t \leq 1000 1≤t≤1000) - 测试用例的数量。测试用例说明如下。
每个测试用例的第一行包含一个整数 n n n ( 1 ≤ n ≤ 5000 1 \leq n \leq 5000 1≤n≤5000) - 字符串 s s s 的长度。
每个测试用例的第二行包含字符串 s s s ( s i ∈ { + , − } s_i \in \{+, -\} si∈{+,−}, ∣ s ∣ = n |s| = n ∣s∣=n)。
请注意,在所有测试用例中, n n n 的总和不受限制。
输出
对于每个测试用例,输出一个整数,代表你可能受到的最小惩罚。
示例
输入
5
1
+
5
-----
6
+-+-+-
10
--+++++++-
20
+---++++-+++++---++-
输出
1
5
0
4
4
注意
在第一个测试用例中,我们有 a = [ 1 ] a = [1] a=[1]。我们可以将数组 a a a 分割为 [ 1 ] [1] [1]。那么,子数组的惩罚总和为 p ( [ 1 ] ) = 1 p([1]) = 1 p([1])=1。
在第二个测试案例中,我们有 a = [ − 1 , − 1 , − 1 , − 1 , − 1 ] a = [-1, -1, -1, -1, -1] a=[−1,−1,−1,−1,−1]。我们可以将数组 a a a 拆分为 [ − 1 ] , [ − 1 ] , [ − 1 ] , [ − 1 ] , [ − 1 ] [-1], [-1], [-1], [-1], [-1] [−1],[−1],[−1],[−1],[−1]。那么,子数组的惩罚总和为 p ( [ − 1 ] ) + p ( [ − 1 ] ) + p ( [ − 1 ] ) + p ( [ − 1 ] ) + p ( [ − 1 ] ) = 1 + 1 + 1 + 1 + 1 = 5 p([-1]) + p([-1]) + p([-1]) + p([-1]) + p([-1]) = 1 + 1 + 1 + 1 + 1 = 5 p([−1])+p([−1])+p([−1])+p([−1])+p([−1])=1+1+1+1+1=5。
在第三个测试案例中,我们有 a = [ 1 , − 1 , 1 , − 1 , 1 , − 1 ] a = [1, -1, 1, -1, 1, -1] a=[1,−1,1,−1,1,−1]。我们可以将数组 a a a 拆分为 [ 1 , − 1 , 1 , − 1 ] , [ 1 , − 1 ] [1, -1, 1, -1], [1, -1] [1,−1,1,−1],[1,−1]。那么,子数组的惩罚总和为 p ( [ 1 , − 1 , 1 , − 1 ] ) + p ( [ 1 , − 1 ] ) = 0 + 0 = 0 p([1, -1, 1, -1]) + p([1, -1]) = 0 + 0 = 0 p([1,−1,1,−1])+p([1,−1])=0+0=0。
解题思路
以划分出的区间的区间和为0为目标进行划分,无法划分出区间和为0的数字就让它自身划分。例如 [ + , + , − , + , − , − , + , ] [+,+,-,+,-,-,+,] [+,+,−,+,−,−,+,]就可以划分成 [ + ] [+] [+]和 [ + , − , + , − , − , + , ] [+,-,+,-,-,+,] [+,−,+,−,−,+,]。然后很容易就可以证出,如果 + + +和 − - −的数量一致无论怎么排序,区间和一定为 0 0 0;如果不一致,这个区间一定可划分成三个区间,其中两个区间的区间和为零,一个区间包含多于的-或者+。那么答案就是 + + +和 − - −的数量差
题解
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>
#define endl '\n'
#define ft first
#define sd second
#define yes std::cout<<"Yes\n";
#define no std::cout<<"No\n";
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef queue <int> qi;
typedef queue <ll> ql;
typedef queue <pii> qpii;
typedef queue <pll> qpll;
typedef queue <psi> qpsi;
typedef queue <psl> qpsl;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpl;
typedef priority_queue<psi> pqpsl;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<string, int> msi;
typedef map<string, ll> msl;
typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;
void cinv(vi vec,int n) {for (int i = 1; i <= (n); i++)cin >> (vec)[i];}
void rcinv(vi vec, int n) {for (int i = (n); i >= 1; i--)cin >> (vec)[i];}
void coutv(vi vec, int n) { for (int i = 1; i <= (n); i++)cout << (vec)[i] << " "; cout << '\n'; }
void rcoutv(vi vec, int n) { for (int i = (n); i >= 1; i--)cout << (vec)[i] << " "; cout << '\n'; }
void solve()
{
ll n;cin>>n;
ll cnt1=0,cnt2=0;
string s;cin>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='+')
cnt1++;
else
cnt2++;
}
cout<<abs(cnt1-cnt2)<<endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C. Grouping Increases
时间限制: 1秒
内存限制: 256兆
输入: 标准输入
输出: 标准输出
You are given an array a a a of size n n n. You will do the following process to calculate your penalty:
- Split array a a a into two (possibly empty) subsequences† s s s and t t t such that every element of a a a is either in s s s or t ‡ t‡ t‡.
- For an array b b b of size m m m, define the penalty p ( b ) p(b) p(b) of an array b b b as the number of indices i i i between 1 1 1 and m − 1 m−1 m−1 where b i < b i + 1 b_i < b_{i+1} bi<bi+1.
- The total penalty you will receive is p ( s ) + p ( t ) p(s) + p(t) p(s)+p(t).
If you perform the above process optimally, find the minimum possible penalty you will receive.
给你一个大小为 n n n 的数组 a a a 。你将按以下步骤计算罚金:
- 将数组 a a a 分割成两个(可能为空)子序列 † ^\dagger † 和 t t t ,这样 a a a 中的每个元素要么在 s s s 中,要么在 s s s 中。 s s s 和 t t t ,这样 a a a 中的每个元素要么在 s s s 中,要么在 t ‡ t^\ddagger t‡ 中。
- 对于大小为 m m m 的数组 b b b ,定义数组 b b b 的惩罚 p ( b ) p(b) p(b) 为 1 1 1 和 m − 1 m - 1 m−1 之间索引 i i i 的个数,其中 b i < b i + 1 b_i< b_{i + 1} bi<bi+1 .
- 你将得到的总惩罚为 p ( s ) + p ( t ) p(s) + p(t) p(s)+p(t) 。
如果以最优方式执行上述过程,请求得可能收到的最小惩罚。
† ^\dagger † 如果 x x x 可以通过删除几个(可能是零个或全部)元素从 y y y 得到,那么序列 x x x 就是序列 y y y 的子序列。
‡ ^\ddagger ‡ 将数组 a = [ 3 , 1 , 4 , 1 , 5 ] a=[3,1,4,1,5] a=[3,1,4,1,5] 拆分为 ( s , t ) (s,t) (s,t) 的有效方法有 ( [ 3 , 4 , 1 , 5 ] , [ 1 ] ) ([3,4,1,5],[1]) ([3,4,1,5],[1]) 、 ( [ 1 , 1 ] , [ 3 , 4 , 5 ] ) ([1,1],[3,4,5]) ([1,1],[3,4,5]) 和 ( [ ] , [ 3 , 1 , 4 , 1 , 5 ] ) ([],[3,1,4,1,5]) ([],[3,1,4,1,5]) ,而拆分为 a a a 的无效方法有 ( [ 3 , 4 , 5 ] , [ 1 ] ) ([3,4,5],[1]) ([3,4,5],[1]) 、 ( [ 3 , 1 , 4 , 1 ] , [ 1 , 5 ] ) ([3,1,4,1],[1,5]) ([3,1,4,1],[1,5]) 和 ( [ 1 , 3 , 4 ] , [ 5 , 1 ] ) ([1,3,4],[5,1]) ([1,3,4],[5,1]) 。
输入
每个测试包含多个测试用例。第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) - 测试用例的数量。测试用例说明如下。
每个测试用例的第一行包含一个整数 n n n ( 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105) - 数组 a a a 的大小。
第二行包含 n n n 个整数 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an ( 1 ≤ a i ≤ n 1 \leq a_i \leq n 1≤ai≤n) - 数组 a a a 的元素。
保证所有测试用例的 n n n 之和不超过 2 × 1 0 5 2 \times 10^5 2×105。
输出
对于每个测试用例,输出一个整数,代表你可能受到的最小惩罚。
示例
输入
5
5
1 2 3 4 5
8
8 2 3 1 1 7 4 3
5
3 3 3 3 3
1
1
2
2 1
输出
3
1
0
0
0
注意
在第一个测试用例中,拆分 a a a 的可能方法是 s = [ 2 , 4 , 5 ] s=[2,4,5] s=[2,4,5] 和 t = [ 1 , 3 ] t=[1,3] t=[1,3]。罚则是 p ( s ) + p ( t ) = 2 + 1 = 3 p(s) + p(t) = 2 + 1 = 3 p(s)+p(t)=2+1=3。
在第二个测试用例中,拆分 a a a 的可能方式是 s = [ 8 , 3 , 1 ] s=[8,3,1] s=[8,3,1] 和 t = [ 2 , 1 , 7 , 4 , 3 ] t=[2,1,7,4,3] t=[2,1,7,4,3]。罚则为 p ( s ) + p ( t ) = 0 + 1 = 1 p(s) + p(t) = 0 + 1 = 1 p(s)+p(t)=0+1=1。
在第三个测试用例中,拆分 a a a 的可能方式是 s = [ ] s=[] s=[] 和 t = [ 3 , 3 , 3 , 3 , 3 ] t=[3,3,3,3,3] t=[3,3,3,3,3]。罚则为 p ( s ) + p ( t ) = 0 + 0 = 0 p(s) + p(t) = 0 + 0 = 0 p(s)+p(t)=0+0=0。
解题思路
我们可以将题目转化一下,这样思考:一开始有两个盒子,每个盒子可以装下比自己小的一个盒子,装下比自己小的盒子之后,容量就会变小,如果两个盒子都装不下,我们就可以花费代价去换一个任意大的盒子,无论多大,花费的代价都是1。现在有一堆盒子等我们装起来,把所有盒子装下的代价是多少。
我们可以一开始看作拥有两个无限大容量的盒子,在装盒子的过程中,如果待装的盒子比现有的两个盒子容量都小,那么肯定是用更小的那个盒子去装,如果用更大的盒子去装,那么浪费的容量就会更大;如果待装的盒子比小盒子大,比大盒子小,那么肯定装进大盒子里,没必要花费代价去换一个盒子;如果待装的盒子比两个盒子都大,那肯定是换掉更小的那个盒子,因为换多大的盒子的代价都一样,既然花的钱一样,肯定是把小的换了留大的。
所以只需要维护两个盒子的实时容量,然后统计换盒子花费的代价就行。
题解
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>
#define endl '\n'
#define ft first
#define sd second
#define yes std::cout<<"Yes\n";
#define no std::cout<<"No\n";
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef queue <int> qi;
typedef queue <ll> ql;
typedef queue <pii> qpii;
typedef queue <pll> qpll;
typedef queue <psi> qpsi;
typedef queue <psl> qpsl;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpl;
typedef priority_queue<psi> pqpsl;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<string, int> msi;
typedef map<string, ll> msl;
typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;
void cinv(vi vec, int n) { for (int i = 1; i <= (n); i++)cin >> (vec)[i]; }
void rcinv(vi vec, int n) { for (int i = (n); i >= 1; i--)cin >> (vec)[i]; }
void coutv(vi vec, int n) { for (int i = 1; i <= (n); i++)cout << (vec)[i] << " "; cout << '\n'; }
void rcoutv(vi vec, int n) { for (int i = (n); i >= 1; i--)cout << (vec)[i] << " "; cout << '\n'; }
void solve()
{
ll n; cin >> n;
int minbox=INT32_MAX;
int maxbox=INT32_MAX;
int now;
int cost=0;
for(int i=0;i<n;i++)
{
cin>>now;
if(minbox>maxbox)// 只需要知道小盒子和大盒子的容量分别是多少就行
swap(minbox,maxbox);
if(now<=minbox)// 比小盒子更小,装进小盒子里
minbox=now;
else if(now>maxbox)// 比大盒子更大,花费1代价换掉小盒子
{
cost++;
minbox=now;
}
else// 比大盒子小且比小盒子大,装进大盒子
maxbox=now;
}
cout<<cost<<endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D题会写了,但是还不能自己证明解法为啥是对的,以后有空补一下吧。
本文标签: 题解codeforces
版权声明:本文标题:codeforces Hello 2024个人题解(A~C) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1725584469a1031031.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论