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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| ## C. Limited Repainting
其实也是临门一脚，已经是想到二分答案了，但是我想到的组织二分答案的方式有问题，比较困难，基本搞不定。（我想枚举的是选择的R连续段的个数，看了题解以后恍然大悟，他枚举的是这个颜色不匹配的的最大允许值）
当然题目也暗示的很明显了，最大值最小，这个算是很明显的暗示了。
```cpp
// Problem: C. Limited Repainting
// Contest: Codeforces - Educational Codeforces Round 175 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2070/problem/C
// Memory Limit: 512 MB
// Time Limit: 2000 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>(3e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,K,T,A[MAXN];
char col[MAXN];
ll ans=0;
inline bool check(ll x){
bool isConti=false;
ll cntop=0;
A[N+1]=INF,col[N+1]='R';
FOR(i,1,N+1){
if(col[i]=='R'){
if(A[i]>x && isConti){
isConti=false;
++cntop;
}
}else{
if(A[i]>x && !isConti){
isConti=true;
}
}
}
if(cntop>K) return false;
return true;
}
inline void solve(){
cin>>N>>K;
ll cntr=0;
FOR(i,1,N){
cin>>col[i];
if(col[i]=='R') ++cntr;
}
ll maxr=0,maxb=0;
FOR(i,1,N){
cin>>A[i];
if(col[i]=='R') maxr=max(maxr,A[i]);
else maxb=max(maxb,A[i]);
}
if(K==0){
cout<<maxb<<"\n";
return;
}
ll l=0,r=max(maxr,maxb);
ans=INF;
while(l<r){
ll mid=l+r>>1;
if(check(mid)){
r=mid;
}else{
l=mid+1;
}
}
cout<<l<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
#ifdef LOCAL
cerr << '\n';
#endif
}
return 0;
}
/*
AC
https://mirror.codeforces.com/contest/2070/submission/308459133
1
32 5
BBBRRBBRBBRBBRBRBBBRRBRBRBBRBRBB
12 13 671 12 1277 13872 112 1381 1213 1918 12 121389 65427 435 21 128 1263 16797 1283974 1268 283738435738 21289738 217123 362182 18189 217 17834 18923 121 4378 642173 847356
*/
|