AtCoder Beginner Contest 320 G - Slot Strategy 2

考虑机器对于每个数字$i$所能达到的最短时间，对于一个数字$i$,若其能够在时间$t$内统一，那么其也一定能在时间$2t$内统一，所以对于每个数字的最小花费具有单调性，因此考虑二分。
考虑二分的check函数，因为同一个时间点我们只能操作一台机器，所以对于n台机器，我们考虑其是否能够在$mid$时间内呈现出数字$i$：由此可以联想到二分图的最大匹配，即我们将n台机器看作左部，将时间看作右部，那么此刻就转换为了该二分图是否匹配。

#include 

using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"

int n,m;
string s[105];
vector<int> e[15][105];//e[i][j]表示第i个数字所在的j机器出现数字i的时间
map<int,int> st,f;//因为值域为1e9，所以使用map，数组没试过memset会不会超时
bool find(int x,int mid,int dig)//匈牙利算法，x为点的下标，mid为时间上限，dig表示第几台机器
{
	for(auto u: e[dig][x]){
		for(int i=u;i<=mid;i+=m){
			if(st[i]) continue;
			st[i]=1;
			if(!f[i]||find(f[i],mid,dig)) {
				f[i]=x;
				return true;
			}
		}
	}
	return false;
}

bool check(int mid,int dig)//check函数，
{
	f.clear();
	for(int i=1;i<=n;i++){
		st.clear();
		if(!find(i,mid,dig)) return false;
	}
	return true;
}


void solve()
{	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		int cnt=0;
		for(auto x: s[i]){
			e[x-'0'][i].push_back(cnt);
			cnt++;
		}
	}
	ll ans=2e9;
	for(int i=0;i<=9;i++){//对于每个数字去二分然后取最小值
		ll res=2e9;
		int l=0,r=n*m;
		while(l<=r){
			int mid=(l+r)/2;
			if(check(mid,i)){
				res=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		ans=min(ans,res);
	}
	if(ans==2e9) cout<<-1<<endl;
	else cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
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