Atcoder Beginner Contest 443 – C
C – Chokutter Addiction
前言
今天接着来水ABC
⚠️警告！！！今天水的题目是第三题！！！
为什么要警告呢？我也不知道……
题目大意
某公司从
0
0
0 时刻开始上班，到
t
t
t 时刻下班 （我猜公司的全体员工都很喜欢
t
t
t 这个数字吧）
高桥在公司的工作时间内会按照以下规则打开
c
h
o
k
u
t
t
e
r
chokutter
chokutter （说白了就是摸鱼）
-
上班的同时打开
c
h
o
k
u
t
t
e
r
chokutter
chokutter
-
如果青木从高桥桌后经过的瞬间高桥正打开
c
h
o
k
u
t
t
e
r
chokutter
chokutter 则关闭
c
h
o
k
u
t
t
e
r
chokutter
chokutter
-
高桥在某个时刻
i
i
i 关闭
c
h
o
k
u
t
t
e
r
chokutter
chokutter 后，一定会在
i
+
100
i+100
i+100 时刻重新打开
c
h
o
k
u
t
t
e
r
chokutter
chokutter
-
从上班到下班期间，青木会从高桥桌后经过
n
n
n 次，每次时间在
a
i
a_i
ai
问：从上班到下班期间总共查看了多长时间
c
h
o
k
u
t
t
e
r
chokutter
chokutter
翻译一下：
高桥在公司的工作时间内会按照以下规则摸鱼
-
上班的同时摸鱼
-
如果被领导看见了，就停止摸鱼
-
停止摸鱼
100
100
100 个时刻后，继续摸鱼
-
从上班到下班期间，领导会检查
n
n
n 次，每次在
a
i
a_i
ai 时刻
问：从上班到下班期间总共摸了多长时间鱼
思路
直接按时间模拟会超时，复杂度
O
(
t
)
O(t)
O(t)
因为题目保证
a
i
a_i
ai 有序，所以无需排序，直接模拟每个检查时间点，数学计算即可，是一道大水题
实现
枚举每个检查时间点并进行计算：
int ans=0;
int st=0; //摸鱼开始时间
for(int i=1;i<=n;i++){
if(st<a[i])ans+=a[i]–st,st=a[i]+100;//领导来了
}
if(st<t){ //还没下班，领导走了
ans+=t–st; //太爽了，摸鱼到下班
}
然后没了，真的没了
AC代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[300010];
signed main(){
int n,t;
cin>>n>>t;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=0;
int st=0; //摸鱼开始时间
for(int i=1;i<=n;i++){
if(st<a[i])ans+=a[i]–st,st=a[i]+100;//领导来了
}
if(st<t){ //还没下班，领导走了
ans+=t–st; //太爽了，摸鱼到下班
}
cout<<ans;
return 0;
}
AC记录
其实可以不开数组的：
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n,t;
cin>>n>>t;
int ans=0;
int st=0; //摸鱼开始时间
for(int i=1;i<=n;i++){
int a;
cin>>a;
if(st<a)ans+=a–st,st=a+100;//领导来了
}
if(st<t){ //还没下班，领导走了
ans+=t–st; //太爽了，摸鱼到下班
}
cout<<ans;
return 0;
}
AC记录
再见
大家再见了！
不过我想问，他每次领导走过来就关，领导走了就开，领导不会发现吗？
领导发现了，不会把他炒了吗？
就不太理解了……
