2012-0008
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
占by大肥羊～此坑必填@.@
这题，在一个城市要不要花钱购买攻击力，取决于这个城市的攻击力收益，注意收益应该是money*sum[i]/a[i]-money,其中sum[i]=sigma(b[j]),(j>=i)我比赛的时候没有把money这个成本剪掉，所以一直错
如果money投到后面的城市有更高的收益，则留给后面
具体的做法和证明，出题人和vout都再forum上写了解体报告，我就搬运一下=_=
by hzwlzrj:
我重新想了一下证明：
首先可以明确的是，由于花钱提升攻击力可以是以任意实数进行的，钱的数目不影响城市的优劣性，并且每一处提升攻击力必然是把所有的钱都投入。
然后我们定义在城市i，攻击力的单价是a[i]，之后得到钱的系数是b[i]，s[i]=b[1]+b[2]+...+b[i-1]，s[n+1]=b[1]+...+b[n]
再定义对于i<j， 城市i比城市j更优表示先在城市i提升攻击力在去j提升，比在i不提升等到j提升要优
城市j比城市i更优表示在i不提升等到j提升，比先在城市i提升攻击力在去j提升要优
1、对于城市i，假设花了c的钱提升攻击力，那么到城市k之前，通过这部分提升的攻击力可以得到的额外金钱是c/a[i]*(s[k]-s[i])。
2、令s[n+2]=+∞，设j是最小的满足c/a[i]*(s[j]-s[i])>=c的正整数，即到达城市j之前，我刚刚可以通过额外提升的攻击力得到比投入更多的钱。（j=n+1表示旅程结束之时）显然，对于任意城市k>=j，i比k更优（因为这样到k时再有更多的钱的同时攻击力更高了）因此我们接着考虑i+1~j-1的城市
3、考虑城市i<k<j，如果j比k优，k比i优，那么j比i优，因此我们只需要考虑在i之后那个最优的城市ii即可。（从最优队列的顶部取得）
4、若ii>=j,i比ii优，把i加入最优队列。若i<ii<j。由于ii比任意k>i都要优，因此在i+1~ii-1之间的城市，我们都不需要去提升攻击力。
因此我们只有两种策略：
①在i提升攻击力，然后在ii提升攻击力。
②只在ii提升攻击力。
这两种策略，在ii提升完毕攻击力（还没有获得金钱）之后，只剩下攻击力一个指数。因此我们只需要通过比较两者的攻击力就可以知道哪个更优。若i比ii优，则把i加入最优队列。
最后只在最优队列提升攻击力，模拟一边就好了。
看一下吧，这个证明有没有问题。
by vout:
我想我已经能够证明我的做法就对的了。
假设用c的钱去升级，那么多赚的钱就是(s[i]-a[i])*c/a[i]，可见升级的两个要素: 1.s[i]>a[i], 2.所有钱都拿去升级。
按照s[i]-a[i]来排序，注意到一点，s[i]是递减的，于是当j>i, s[j]-a[j] > s[i]-a[i]时，必然有a[j] < a[i]。于是如果把i的钱留到j再用，就有：
(s[i]-a[i])*c/a[i] < (s[j]-a[j])*c/a[j]，也就是放到j那天来用收益更大。
下面只要再证明一点，就是当j>i, s[j]-a[j] > s[i]-a[i]时，不可能出现sum{b[i...j-1]} > a[i]的情况。
否则sum{b[i...j-1]} - a[i] > 0, s[j]-a[j] > s[i]-a[i], 两式相加，就有s[i]-a[i]-a[j]>s[i]-a[i]，这就矛盾了。综上，我的做法应该是正确的。占by大肥羊～此坑必填@.@
这题，在一个城市要不要花钱购买攻击力，取决于这个城市的攻击力收益，注意收益应该是money*sum[i]/a[i]-money,其中sum[i]=sigma(b[j]),(j>=i)我比赛的时候没有把money这个成本剪掉，所以一直错
如果money投到后面的城市有更高的收益，则留给后面
具体的做法和证明，出题人和vout都再forum上写了解体报告，我就搬运一下=_=
by hzwlzrj:
我重新想了一下证明：
首先可以明确的是，由于花钱提升攻击力可以是以任意实数进行的，钱的数目不影响城市的优劣性，并且每一处提升攻击力必然是把所有的钱都投入。
然后我们定义在城市i，攻击力的单价是a[i]，之后得到钱的系数是b[i]，s[i]=b[1]+b[2]+...+b[i-1]，s[n+1]=b[1]+...+b[n]
再定义对于i 城市j比城市i更优表示在i不提升等到j提升，比先在城市i提升攻击力在去j提升要优 1、对于城市i，假设花了c的钱提升攻击力，那么到城市k之前，通过这部分提升的攻击力可以得到的额外金钱是c/a[i]*(s[k]-s[i])。 2、令s[n+2]=+∞，设j是最小的满足c/a[i]*(s[j]-s[i])>=c的正整数，即到达城市j之前，我刚刚可以通过额外提升的攻击力得到比投入更多的钱。（j=n+1表示旅程结束之时）显然，对于任意城市k>=j，i比k更优（因为这样到k时再有更多的钱的同时攻击力更高了）因此我们接着考虑i+1~j-1的城市 3、考虑城市i 4、若ii>=j,i比ii优，把i加入最优队列。若i 因此我们只有两种策略： ①在i提升攻击力，然后在ii提升攻击力。 ②只在ii提升攻击力。 这两种策略，在ii提升完毕攻击力（还没有获得金钱）之后，只剩下攻击力一个指数。因此我们只需要通过比较两者的攻击力就可以知道哪个更优。若i比ii优，则把i加入最优队列。 最后只在最优队列提升攻击力，模拟一边就好了。 看一下吧，这个证明有没有问题。 by vout: 我想我已经能够证明我的做法就对的了。 假设用c的钱去升级，那么多赚的钱就是(s[i]-a[i])*c/a[i]，可见升级的两个要素: 1.s[i]>a[i], 2.所有钱都拿去升级。 按照s[i]-a[i]来排序，注意到一点，s[i]是递减的，于是当j>i, s[j]-a[j] > s[i]-a[i]时，必然有a[j] < a[i]。于是如果把i的钱留到j再用，就有： (s[i]-a[i])*c/a[i] < (s[j]-a[j])*c/a[j]，也就是放到j那天来用收益更大。 下面只要再证明一点，就是当j>i, s[j]-a[j] > s[i]-a[i]时，不可能出现sum{b[i...j-1]} > a[i]的情况。 否则sum{b[i...j-1]} - a[i] > 0, s[j]-a[j] > s[i]-a[i], 两式相加，就有s[i]-a[i]-a[j]>s[i]-a[i]，这就矛盾了。综上，我的做法应该是正确的。