自动搬运

查看原文

来自洛谷，原作者为

	CSP_Sept 私が戻ってきたのはね。 もう一度、星の音を聞くためだよ

搬运于2025-08-24 22:33:00，当前版本为作者最后更新于2021-08-05 10:00:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题号 7777 留念（

Description

给定 $n$，要求把 $1\sim n$ 取完，有两种取法：

1. 单独取 $i$，代价 $i\times p$。
2. 一起取 $i,j$，代价 $|i-j|\times q$。

求最小代价。

Solution

首先观察到两个显然的性质：

• 开始使用方法 2 后，一直使用方法 2 是最优的。
• 使用方法 2 时，保证 $|i-j|=1$ 是最优的。

我们考虑何时开始使用方法 2。

对于 $i,i+1$，有两种代价：$(2i+1)\times p$ 和 $q$。

于是，当 $(2i+1)\times p\ge q$ 且 $n-i-1$ 为偶数时，我们就开始使用方法 2。

$n-i-1$ 为偶数是保证开始使用方法 2 后可以一直使用方法 2（剩余数字数量为偶数）。

Code

#include <cstdio>
#include <cmath>

#define ll long long
using namespace std;
ll p, q, n;
void sol(){
    scanf("%lld%lld%lld", &n, &p, &q);
    if(p == 0){
    	puts("0");
    	return;
	}
	if(n == 1){
		printf("%lld\n", p);
		return;
	}
	ll x = q / p;
	x = (x - 1) / 2;
	ll res = n - x;
	ll ans = 0;
	if(res % 2) x++, res--;
	ans = x * p;
	ans += (x - 1) * x * p / 2;
	ans += (res / 2) * q;
	printf("%lld\n", ans);
}
int main(){
	//freopen("tmp.in", "r", stdin);
	//freopen("tmp.out", "w", stdout);
	int t;
	scanf("%d", &t);
	while(t--) sol();
	return 0;
}