CSP-J2

发表于 | 更新于 | 阅读次数：
本文字数： 8.9k | 阅读时长 ≈ 8 分钟

前言

今天写的是关于CSP-J2的一些事情。

刚刚把日记给删了，唉，又要重新写。

从今天起，我要每一天写一篇日记，不论长度。

P5660 数字游戏

P5660 数字游戏

来说一下这道题目吧。

这一道题目就是读入一个字符串然后统计字符串里面的1的个数。

思路

模拟+暴力

先用一个Len记录字符串长度 length(),然后在用循环统计。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main()
{
	string S1;
	cin>>S1;//读入
	int Len,ans;//Len记录长度，ans记录一的个数。
	Len=S1.length();//长度测量
	for (int i=1;i<=Len;i++)
	{
		if (S1[i]=='1') ans++;
	}//循环统计
	cout<<ans<<endl;//输出
	return 0;
}

过了样例。

于是，我兴高采烈地交上去。

…

全炸，一片红色！

问题是什么呢？

debug

发现了！！这个cin从0开始读入，但我是从1开始处理的(其实如果我测试了样例2 就不会有悲剧了，唉)。

于是，我又兴高采烈地交上去。

…

又全炸？？？

然后我在Linux上运行了一下发现，ans没有设成0。

然后我又双叒叕兴高采烈地交上去。

…

AC了！！！nice

看来不能熬夜了。

今天到此结束。

ByeBye

2019.11.23 19:51 更新

P5661 公交换乘

P5661 公交换乘

题目理解

题目有那么一点复杂，不过，认真读题的话你会发现，这其实很简单。

题目大意

就是现在要搭乘地铁和公交车，那么搭乘一次地铁之后有一张优惠券，有效期为45分。在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟。

那么还有条件，优惠券可以积累，可以使用优惠券一定用优惠券，如果有多种优惠券，先使用最早的。

分析题目

其实题目很简单。

思路：模拟+暴力怎么又是模拟+暴力，看了今年J2的出题人很喜欢模拟。

首先我们边读入边处理

那么用一个数组记录优惠券，然后如果是搭乘公交车那么把优惠券都搜索一遍，看那个符合。

再利用一个数字记录优惠券的数量。

看到这里你应该会写了吧。但是别急因为这个思路不能满分。

代码

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
#include <iostream>//头文件不提了
#define INF 100005//宏定义
using namespace std;
int n,sj2[INF],yu2[INF],r,ans=0;//r记录有几张优惠券，sj2代表第几张优惠券的时间，yu2代表第几张优惠券的金额，ans代表用的钱数。
int main() {
	cin>>n;
	for (int i=1; i<=n; i++) {
		int pd,yu,sj;//pd变量是用来判断是公交还是地铁，yu代表几元，sj代表时间
		cin>>pd>>yu>>sj;
		if (!pd) {//如果是地铁那么处理开始
		    r++;//优惠券+1
			yu2[r]=yu;//记录第r张优惠券有几元
			sj2[r]=sj;//记录第r张优惠券是什么时间
			ans+=yu;//然后加上花的钱
		} else {
			bool flag=1;//判断能否用优惠券
			for (int j=1; j<=r; j++) {//从一查找到r
				if (sj-sj2[j]>45) continue;//如果时间超过了sj那么continue
				if (yu<=yu2[j]) {//如果金额在yu里面那么可以用
					yu2[j]=-1;//用过一次就不能在用
					flag=0;
					break;//跳出循环
				}
			}
			if (flag) ans+=yu;//如果不能用那么金额加上它
		}
	}
	cout<<ans<<endl;//输出总金额
	return 0;
}

好了我做完了，于是，我兴高采烈地交了上去。

…

TLE TLE TLE

只能拿个50分

debug

这道题到底哪里可以优化呢？

发现了，这个题目有一个隐藏的条件，那就是，时间是一个递增的序列。

那么如果这个优惠券不可以用，之后的公交乘坐也不能用。

那么怎么解决呢？

我们可以设置一个右指针l，然后 for j l -> r 搜一遍，这样一来，就不会超时了。

要注意这个地方，如果你时间>一张优惠券的时间，那么l++ 就是说手动废弃这一张优惠券。

调试完了之后

…

AC了 nice !

好了，已经20:30了，ByeBye！

-------- 本文结束 感谢阅读 --------