CSP-J 前三题详解

没写完。先补会儿文化课作业，等会再回来继续写。

T1 P9748 [CSP-J 2023] 小苹果

令苹果数量为 \(\texttt{n}\)。
容易发现，拿苹果就是每三个一组，取第一个。
需要注意的是，如果以三个一组来考虑拿苹果，最后几个苹果不满三个时也应该算一个组，第一个也要拿走。
形式化的，即当 \(\texttt{n} \bmod 3 \ne 0\) 时，\(\texttt{n} / 3 + 1\) 这个苹果也要被拿走。

第一个小问题通过模拟题意即可解决，判断当前所有苹果是不是刚好可以分成三个三个一组，可以的话就拿走 \(\texttt{n} / 3\) 个，
否则拿走 \(\texttt{n} / 3 + 1\) 个苹果。
形式化的，即为判定 \(\texttt{n} \bmod 3 = 0\) 是否为真。

那么同时，拿走最后一个苹果的判断方式便十分显然了：
关注最后的这一组，如果拿走的这个苹果正是序列最后一个苹果，那么第二个小问题便迎刃而解。
即：每次拿走判断 $\texttt{n} =1 $ 是否成立，成立则最后一组被拿走的便是整个序列的最后一个苹果，即开始时编号为 \(\texttt{n}\) 的苹果。

代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
 
int main(){
	cin>>n;
	ll ans=0; // ans 表示这队苹果要用多少次才可以取完。
	ll tans=0; // tans 表示最后一个苹果，即编号为 n 的 苹果，是什么时候拿走的。
	while(n){
		if(n%3==1 && tans==0) { tans=ans+1; } // 先判断本轮是否可以拿走第 n 个苹果，如果可以，那么拿走他的应该就是这一次。
                                              // 需要注意的是，由于本轮还未开始统计，所以要用 ans+1 来维护 tans 。
                                              // 另外需要注意的是，最后一个取走了会有前一个苹果成为最后一个，所以要特判是否已经被取走来锁定答案。		
			ans++;	
			n-=ceil(1.0*n/3); // 向上取整，规避判断 n%3==0 是否成立。需要注意把 n 换为浮点数避免整型计算直接给小数部分干没了。
	}
		cout<<ans<<" "<<tans<<endl;
	

	return 0;
}

T2 P9749 [CSP-J 2023] 公路

一开始的想法是用单调栈维护每一个加油站之后最便宜的加油站是谁，这样在每个加油站贪心的加好刚刚够的油开到更便宜的加油站即可。
但是我的代码能力太弱了不知道哪里打挂了。
而且这个方法也不够优雅。

于是下面介绍一个一轮过得答案的方法。