CSP-J 2023 T1小苹果 T2公路

[CSP-J 2023] T1 - 小苹果

每隔两个苹果取一个苹果，也就是每三个苹果取一个苹果，此时肯定需要在与模$3$有关的基础上进行分类讨论：

• 当$n\%3==0$时，此时n可以整除3，每次可以取$\frac{n}{3}$个苹果。
• 当$n\%3!=0$时，每次可以取$\lceil \frac{n}{3}\rceil$个苹果。

此时我们可以使用循环来模拟拿苹果的过程，不需要知道每次拿的是哪几个苹果，只需要知道每次拿了几个苹果，每次更新苹果的数量，当苹果被取完时循环结束。$ans$即为拿苹果的次数。

while (n) {
	ans++;
	if (n % 3 == 0) n = n - n / 3;
	else n = n - (n / 3 + 1);
}

除此之外，题目还要求编号为$n$的苹果是第几次被拿走的，由于我们每次拿的是最左边的苹果，当编号为$n$的苹果在某一块的最左侧时，此时就可以拿到这个编号为$n$的苹果，也就是当$n\%3==1$时。

最后可以检查一下复杂度，每次都会拿走至少$\frac{1}{3}$的苹果，也就是苹果每次会变成其原来的$\frac{2}{3}$倍，$n$最大是$1e9$，设最后执行了$t$次，则$1e9\ast (\frac{2}{3}{)}^t=1$，$t$的值是$50$左右，复杂度完全没问题。

#include <bits/stdc++.h>

using namespace std;
int n, ans, t;

int main(int argc, char const *argv[]) {
	cin >> n;
	while (n) {
		ans++;
		if (n % 3 == 1 and !t) t = ans; 
		if (n % 3 == 0) n = n - n / 3;
		else n = n - (n / 3 + 1);
	}
	cout << ans << " " << t << endl;
}

[CSP-J 2023] T2 - 公路

本题的油箱无限大，所以当一个点的油价很便宜时，我们要在这个点买足够多的油，这个足够多的限制在哪里？就是能够支撑我们到下一个更便宜的点。至此思路就很明显了，在起点处是必须要买油的，当遇到一个比起点更低价格的点时，计算这两个点之间的距离（前缀和），用起点的价格买足够多的油，来到这个点之后继续向后寻找更便宜的油。

要注意的点是买的油一定是整数，例如点$1$与点$2$的距离是$10$，每升油能让我们走$4$，在起点处就必须买$3$升油（$3\ast 4=12>10$）如果点$1$与点$2$的距离是$12$，我们还是需要买$3$升油，所以要买的油的数量$x$与距离$distance$的关系是$x=\lceil \frac{distance}{d}\rceil$，具体写代码时，为了避免浮点数或者取整操作，我们可以使$x=\frac{distance+d-1}{d}$，这个式子和上式是等价的，例如$\frac{10+4-1}{4}=3$，$\frac{12+4-1}{4}=3$。另外，到达点$2$之后我们还剩$2$升油，这$2$升油是可以继续用的。

最终车一定要开到$n$号点，所以如果在最后一个点时没有更新更便宜的油价，那么终点到上一个便宜点之间的距离是会被忽略的。所以最后要加一下开到终点的花费。

#include <bits/stdc++.h>
#define A 100010

using namespace std;
typedef long long ll;
int n, v[A], a[A];
ll ans, d, sum[A];

int main(int argc, char const *argv[]) {
	cin >> n >> d;
	for (int i = 2; i <= n; i++) {
		scanf("%d", &v[i]);
		sum[i] = sum[i - 1] + v[i];
	}
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int pos = 1;
	ll oil = 0, leftoil = 0, minn = a[1];
	for (int i = 2; i <= n; i++) {
		if (a[i] < minn) {
			oil = (sum[i] - sum[pos] - leftoil + d - 1) / d;
			leftoil += oil * d - (sum[i] - sum[pos]);
			ans += oil * minn;
			minn = a[i];
			pos = i;
		}
	}
	ans += (sum[n] - sum[pos] - leftoil + d - 1) / d * minn;
	cout << ans << endl;
}

由于做法中出现了乘法，所以代码写出之后需要关注一下是否会爆$int$，每个变量的数据范围都是$1e5$，前缀和$sum[n]=n\ast v[i]=1e10$会爆$int$，$oil\ast d$和$oil\ast minn$也有可能爆$int$，需要给相应的变量开上$longlong$。