自动搬运

查看原文

来自洛谷，原作者为

	Wind_Smiled 风颜悦。颜悦因风起，风起故颜悦。||向着不同的方向、我们逐渐远去、背对背的你我、难能再见||这个OP的 uid：266896259

搬运于2025-08-24 22:26:30，当前版本为作者最后更新于2022-09-07 16:09:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

有一行 $n$ 个空位。 有一些能源装置，每个能源装置会占用 $1$ 或 $2$ 个空位，并且每回合产生一个单位的能量。每个回合可以建造一个新的能源装置（也可以不建造）。如果没有地方建新的能源装置，可以拆除一些旧的能源装置。每一回合过后，统计这一回合内所有已经建造的能源装置产生的能量，并将其加到总分中。 现在求可能的最大得分。

贪心

因为每一种能源装置产出能量相等，所以在贪心算法中的条件判断式有三个：

1. 尽可能地放置占位为 $1$ 的装置。
2. 若剩余位数为 $0$ 且有一个或以上的占位为 $2$ 的装置，则将一个占位为 $2$ 的装置拆除，并更换为占位为 $1$ 的装置。
3. 若条件 $1,2$ 都不成立，且剩余位数大于等于 $2$，则放置占位为 $2$ 的装置。

用变量 $one,two$ 分别记录占位为 $1,2$ 的装置数，$ans$ 记录总得分，$s$ 记录每回合安装的装置的占位（$s_i$ 访问每一位进行判断，因为题中未给出回合总数）。

$n$ 作为空位总数，可以用自增自减来模拟安装装置后的空位数 ，减去相对应的占位数，对应的种类的个数加一。

对于贪心的条件 $2$ ，我们让条件表达式为：n==0&&two>=1，因为若 $n=1$，则还能安装，若 $two \ge 1$ 则可以拆除一个，安装为占位为 $1$ 的装置（在此处会增加 $2$ 个空位，再减少 $1$ 个空位，总空位数会增加 $1$）。

毒瘤

• 在这个题目里，数据还是挺毒瘤的，不开 long long 见祖宗。

• 因为题中未给出回合总数，要用 string 类存储。

#include<bits/stdc++.h>
using namespace std;
long long n,ans,one,two;
string s;
int main(){
	cin>>n>>s;
	for(long long i=0;i<s.size();i++){
		if(s[i]=='1'){
			if(n>=1){
				one++;
				n--;
			}
			else if(n==0&&two>=1){
				two--;
				one++;
				n++;
			}
		}
		else if(s[i]=='2'){
			if(n>=2){
				two++;
				n-=2;
			}
		}
		ans=ans+one+two;
	}
	cout<<ans;
	return 0;
}