Znzryb's Blog
0%

C. Competitive Fishing（通过最少的分段，来让Bob-Alice≥k）

Posted on Edited on

思路讲解

需要综合计量一个分割点的价值。之前迟迟无法AC就是这个原因。

Call.push_back(Cnt1[i]-Cnt0[i]);

一个分割可以产生的相差值就是Cnt1[i]−Cnt0[i]Cnt1[i]-Cnt0[i]，我们把所有分割点产生的相差值push进这个Call里

然后最后sort一下，贪心的减少，统计数量即可。

1
2
3
4
5
6
7
8
9
10
11
12
sort(Call.begin(), Call.end());
ll diff=curBob-curAli;
for(int i=0;i<Call.size();++i){
	diff-=Call[i];
	if(diff==k){
		cout<<cntSplit-i-1<<endl;
		break;
	}else if(diff<k){
		cout<<cntSplit-i<<endl;
		break;
	}
}

AC代码

https://codeforces.com/contest/2042/submission/294590561

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,k;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n>>k;
		vector<ll> A(n+10,0);
		for(int i=1;i<=n;++i){
			char a;
			cin>>a;
			A[i]=a-'0';
		}
		// 0 表示被Alice捕获，1表示被Bob捕获
		// 怎么分让Bob分比Alice分大至少k？而且分最少的组
		vector<ll> Cnt1(n+10,0);
		vector<ll> Cnt0(n+10,0);
		for(int i=n;i>=1;--i){
			if(A[i]){
				Cnt1[i]=Cnt1[i+1]+1;
				Cnt0[i]=Cnt0[i+1];
			}else{
				Cnt0[i]=Cnt0[i+1]+1;
				Cnt1[i]=Cnt1[i+1];
			}
		}
		ll upS=n+1,curBob=0,curAli=0,cnt1Up=0,cnt0Up=0,cntSplit=1;
		vector<ll> /*C1,C0,*/Call;	// 记录分割点可产生的不同值
		for(int i=n;i>=2;--i){
			if(Cnt1[i]>Cnt0[i]){
				// 之前的所有出现过的1都要再加一遍
				curBob+=Cnt1[i]-Cnt1[upS]+cnt1Up;	
				cnt1Up+=Cnt1[i]-Cnt1[upS];
				curAli+=Cnt0[i]-Cnt0[upS]+cnt0Up;
				cnt0Up+=Cnt0[i]-Cnt0[upS];
				Call.push_back(Cnt1[i]-Cnt0[i]);
				cntSplit+=1;
				upS=i;
			}
		}
		if(curBob-curAli<k){
			cout<<-1<<endl;
			continue;
		}
		// 一个分隔点贡献了多少的不同
		sort(Call.begin(), Call.end());
		ll diff=curBob-curAli;
		for(int i=0;i<Call.size();++i){
			diff-=Call[i];
			if(diff==k){
				cout<<cntSplit-i-1<<endl;
				break;
			}else if(diff<k){
				cout<<cntSplit-i<<endl;
				break;
			}
		}
	}
	return 0;
}
// AC https://codeforces.com/contest/2042/submission/294590561

/*
1
5 6
01011

1
5 2
01011

应该输出2 010｜11

wrong answer 48th numbers differ - expected: '2', found: '3'
*/

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

之前一直无法AC就是因为没发现一个点产生的不同值