目录
CSP2019 J2
题目传送
P5660 [CSP-J2019] 数字游戏
- 解析：简单题，没说的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int ans=0;
string s; cin>>s;
for(int i=0; i<s.size(); i++){
if(s[i]=='1') ans++;
}
cout<<ans<<endl;
return 0;
}
P5661 [CSP-J2019] 公交换乘
解析：也是一个模拟题，可以直接暴力模拟
-
如果是 subway， money+=price.
-
如果是 bus，看有没有免费票
-
免费票的查询可以每次从第一次行程开始，但是这样复杂度为 O(n^2)会超时。
-
所以可以根据时间限制 45 分钟进行优化，开一个pre记录当前最早可用票的位置，这样复杂度整体可以维护在 O(n)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int n,op[N],t[N],price[N],pre=1;
LL money=0;
int main(){
// freopen("data.in", "r", stdin);
cin>>n;
for(int i=1; i<=n; i++) cin>>op[i]>>price[i]>>t[i];
for(int i=1; i<=n; i++){
if(op[i]==0){ // subway
money += price[i];
}else if(op[i]==1){// bus
while(t[i]-t[pre] > 45) pre++;//时间优化
int flag=0,p=pre;
while(p<i){ // 找免费票
if(op[p]==0&&t[i]-t[p]<=45&&price[i]<=price[p]){
t[p]=-50, flag=1; break;
}
p++;
}
if(flag==0) money+=price[i];
}
}
cout<<money<<endl;
return 0;
}