Codeforces 1132D Stressful Training 题解
题意
有$n$个学生打比赛,第$i$个学生的电脑的初始电量为$a_i$,每分钟使用的电量为$b_i$(即如果在一分钟的开始有$c$格电量,在下一分钟的开始,电量变为$c-b_i$)。整场比赛持续$k$分钟($1\le n\le 2\times10^5,1\le k\le 2\times10^5,1\le a_i\le 10^{12},1\le b_i\le 10^7$)。
在比赛的开始时有一个充电器。你可以选择充电器的输出电量$x$,$x$为一个非负整数,且以后不能更改。在每一分钟的开始,你可以把充电器插在任意一个学生的电脑上(如果一个电脑的用电量为$b_i$,插入了充电器后每分钟会消耗$b_i-x$格电)。每个学生的电脑的电量没有上限。充电器在一个时刻最多给一台电脑充电。
一个学生成功地完成比赛如果在比赛的过程中他的电脑的电量总是一个非负数。比赛结束时电脑的电量无关紧要。
输出充电器最小的输出电量,使得所有的学生都可以成功地完成比赛,或者输出$-1$表示不可能。
题解
考虑二分 充电器的电量。
如果充电器的电量为$x$,$x=y$时可行,则$x=y+1$时一定可行,而$x=y-1$时则不一定。
二分下限为$0$,上限为$2\times10^{12}$就够了(如果您不想算,设为$10^{18}$也可以,欺负log)。
check
函数考虑贪心:每次选出当前最快要没电的电脑,给它充一分钟电。
显然,如果一台电脑当前电量为$x$,每分钟消耗的电量为$y$,则给它充电使得它的电量非负的最后时刻为$\left\lfloor\frac{x}{y}\right\rfloor+1$。使用优先队列维护即可。
这样check
函数的时间复杂度为$O((n+k)\times\log n)$,总共为$O(\log\text{ans}\times(n+k)\times \log n)$。有点危险:如果优先队列里维护的是pair<long long,pair<long long> >
可能会TLE 50
,改为结构体擦边AC
。
考虑优化:
开$k$个vector
,其中第$i$个维护哪些电脑能支撑到的最后时刻为$i$。其它思路同上。
这样check
函数的时间复杂度为$O(n+k)$,总共为$O(\log\text{ans}\times(n+k))$。
程序
未优化版本
pair<long long,pair<long long> >
:struct
: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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
// #pragma comment(linker,"/STACK:102400000,102400000")
// #include <bits/stdc++.h>
// #include <conio.h>
// #include <windows.h>
using namespace std;
typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef float fl;
typedef double ld;
typedef long double LD;
typedef pair<int,int> pii;
const int INF=1061109567;
const int NINF=-1044266559;
const LL LINF=4557430888798830399;
const ld eps=1e-15;
/*
#define MB_LEN_MAX 5
#define SHRT_MIN (-32768)
#define SHRT_MAX 32767
#define USHRT_MAX 0xffffU
#define INT_MIN (-2147483647 - 1)
#define INT_MAX 2147483647
#define UINT_MAX 0xffffffffU
#define LONG_MIN (-2147483647L - 1)
#define LONG_MAX 2147483647L
#define ULONG_MAX 0xffffffffUL
#define LLONG_MAX 9223372036854775807ll
#define LLONG_MIN (-9223372036854775807ll - 1)
#define ULLONG_MAX 0xffffffffffffffffull
*/
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout)
inline int Read()
{
int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return w?-x:x;
}
inline void Write(int x){if(x<0)putchar('-'),x=-x;if(x>9)Write(x/10);putchar(x%10+'0');}
inline LL powmod(LL a,LL b){LL res=1;a%=MOD;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res%MOD;}
inline LL gcdll(LL a,LL b){return b?gcdll(b,a%b):a;}
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={1,0,-1,0,-1,-1,1,1};
/************************************************************BEGIN************************************************************/
const int maxn=200010;
int n,m;
LL a[maxn],b[maxn];
struct stu
{
LL x,y,r;
inline bool operator <(stu S) const
{
return r>S.r;
}
};
inline bool check(LL mid)
{
priority_queue<stu> q;
rep1(i,n) q.push({a[i],b[i],a[i]/b[i]});
rep1(i,m)
{
LL x=q.top().x,y=q.top().y,r=q.top().r+1;q.pop();
if(r<i) return 0;
if(r>=m) return 1;
x+=mid;
q.push({x,y,x/y});
}
return 1;
}
int main()
{
SF("%d%d",&n,&m);
rep1(i,n) SF("%lld",&a[i]);
rep1(i,n) SF("%lld",&b[i]);
LL l=0,r=1e18; // [l,r)
while(l<r)
{
LL mid=(l+r)/2;
if(check(mid)) r=mid; else l=mid+1;
}
if(check(r)) PF("%lld",r); else PF("-1");
return 0;
}
/*************************************************************END**************************************************************/
优化版本
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
// #pragma comment(linker,"/STACK:102400000,102400000")
// #include <bits/stdc++.h>
// #include <conio.h>
// #include <windows.h>
using namespace std;
typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef float fl;
typedef double ld;
typedef long double LD;
typedef pair<int,int> pii;
const int INF=1061109567;
const int NINF=-1044266559;
const LL LINF=4557430888798830399;
const ld eps=1e-15;
/*
#define MB_LEN_MAX 5
#define SHRT_MIN (-32768)
#define SHRT_MAX 32767
#define USHRT_MAX 0xffffU
#define INT_MIN (-2147483647 - 1)
#define INT_MAX 2147483647
#define UINT_MAX 0xffffffffU
#define LONG_MIN (-2147483647L - 1)
#define LONG_MAX 2147483647L
#define ULONG_MAX 0xffffffffUL
#define LLONG_MAX 9223372036854775807ll
#define LLONG_MIN (-9223372036854775807ll - 1)
#define ULLONG_MAX 0xffffffffffffffffull
*/
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout)
inline int Read()
{
int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return w?-x:x;
}
inline void Write(int x){if(x<0)putchar('-'),x=-x;if(x>9)Write(x/10);putchar(x%10+'0');}
inline LL powmod(LL a,LL b){LL res=1;a%=MOD;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res%MOD;}
inline LL gcdll(LL a,LL b){return b?gcdll(b,a%b):a;}
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={1,0,-1,0,-1,-1,1,1};
/************************************************************BEGIN************************************************************/
const int maxn=200010;
int n,m;
LL a[maxn],b[maxn];
vector<pair<LL,LL> > stu[maxn];
inline bool check(LL mid)
{
rep(i,m+1) stu[i].clear();
rep1(i,n) if(a[i]/b[i]+1<=m) stu[a[i]/b[i]+1].push_back({a[i],b[i]});
int k=1;
rep1(i,m)
{
while(stu[k].empty()) k++;
if(k<i) return 0;
if(k>=m) return 1;
LL x=stu[k].back().fs+mid,y=stu[k].back().sc;stu[k].pop_back();
if(x/y+1<=m) stu[x/y+1].push_back({x,y});
};
return 1;
}
int main()
{
SF("%d%d",&n,&m);
rep1(i,n) SF("%lld",&a[i]);
rep1(i,n) SF("%lld",&b[i]);
LL l=0,r=1e18; // [l,r)
while(l<r)
{
LL mid=(l+r)/2;
if(check(mid)) r=mid; else l=mid+1;
}
if(check(r)) PF("%lld",r); else PF("-1");
return 0;
}
/*************************************************************END**************************************************************/