P7083 [NWRRC2013] Energy Tycoon
Wind_Smiled
·
·
题解
题意
有一行 n 个空位。
有一些能源装置，每个能源装置会占用 1 或 2 个空位，并且每回合产生一个单位的能量。每个回合可以建造一个新的能源装置（也可以不建造）。如果没有地方建新的能源装置，可以拆除一些旧的能源装置。每一回合过后，统计这一回合内所有已经建造的能源装置产生的能量，并将其加到总分中。
现在求可能的最大得分。
贪心
因为每一种能源装置产出能量相等，所以在贪心算法中的条件判断式有三个：
- 尽可能地放置占位为 1 的装置。
- 若剩余位数为 0 且有一个或以上的占位为 2 的装置，则将一个占位为 2 的装置拆除，并更换为占位为 1 的装置。
- 若条件 1,2 都不成立，且剩余位数大于等于 2，则放置占位为 2 的装置。
用变量 one,two 分别记录占位为 1,2 的装置数，ans 记录总得分，s 记录每回合安装的装置的占位（s_i 访问每一位进行判断，因为题中未给出回合总数）。
对于贪心的条件 $2$ ，我们让条件表达式为：`n==0&&two>=1`，因为若 $n=1$，则还能安装，若 $two \ge 1$ 则可以拆除一个，安装为占位为 $1$ 的装置（在此处会增加 $2$ 个空位，再减少 $1$ 个空位，总空位数会增加 $1$）。
#### ~~毒瘤~~
+ 在这个题目里，数据还是挺毒瘤的，~~不开 `long long` 见祖宗。~~
+ 因为题中未给出回合总数，要用 `string` 类存储。
```cpp
#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;
}
```