题解 P4851 【yyf hates ganhuodong】

ouuan

2018-08-26 09:05:27

Solution

就是一道纯模拟题..玩过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; } ```