题解 P4851 【yyf hates ganhuodong】
ouuan
2018-08-26 09:05:27
就是一道纯模拟题..玩过sif的可以秒切了,没玩过的照着“形式化说明”就可以写了。
怎么说,其实也能算是一道入门难度的贪心?
能进行操作 $1$ 就进行操作 $1$ ,否则进行操作 $2$ ,直到活动 $\mathrm{pt} \ge y$
~~假装这是一道贪心题~~,贪心策略的证明就是先进行操作 $1$ 可以提高 $\mathrm{LP}$ 上限,然后操作 $2$ 能恢复的 $\mathrm{LP}$ 就会变多
时间复杂度:$O(\text{能过})$
期望得分:$100$ 分
~~代码注释被形式化说明吃了~~
### 赛后补充
> 由于你可以选择在任意时候打歌且打歌不计时间,每小时恢复和一开始就恢复是等价的...
本来以为有了形式化说明这里不会有问题的...
另外看不懂的真的可以只看形式化说明...
另外本来这题数据是纯随机的,后来我突然想试着卡一卡,就造了两个如果按大于(没有等于)做会WA的点,竟然真的卡到了好多人..
然而除了0/96/100的其它分我是真的没想到..
### UPD
我知道78分是怎么回事了..有的点会无限升级从而有无限lp,有lp无限打歌的算法就挂了
### 标程
```
#include <iostream>
using namespace std;
int main()
{
int a,b,c,d,e,f,g,h,k,x,y,pt=0,ans=0;
cin>>a>>b>>c>>d>>e>>f>>g>>h>>k>>x>>y;
d+=x;
while (pt<y)
{
if (d>=b)
{
pt+=a;
f+=g;
if (f>=e)
{
d=d-b+c+h;
c+=h;
f-=e;
e+=k;
}
else
{
d-=b;
}
}
else
{
++ans;
d+=c;
}
}
cout<<ans;
return 0;
}
```