盒子

[hdu4803/NJUST1786]贪心

//当时做这道题的时候误入了搜索坑,于是就没爬出来。后来知道用贪心,就YY了一个做法,没想到居然还对了。
题目:NJUST1786
据说hdu4803的数据比较水,njust的还不错。。。【两遍都A了思路应该没问题了。。。

题意:
一共有两个按钮,第一个按钮增加物品数量,第二个按钮增加物品总价格,问最少按按钮的次数。

很明显的贪心,因为在物品数量少的时候按第二个按钮总会对最终的结果增加的多一些。
网上的代码大多不优雅,这里提供一种优雅的代码。

首先用ai代表当第一个按钮按到i的时候,按动一次第二个按钮对结果的影响量。
很容易想到第一个按钮必须要按n-1次,那么它对第二个数字的影响量是n-1。因此按动第二个按钮对第二个数字的影响量应该至少是m-n,即变化区间是[m-n,m-n+1)。
令k为按动按钮对第二个数字可造成的影响量的最大值,则k=m-n+1-eps。(如果令k=m-n,变化的区间会变成(m-n-1,m-n])
之后就不断用k去除以a[i]来计算当第一个按钮按到i时第二个按钮最多按动的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<iostream>
using namespace std;
double a[15],k;
const double eps = 1e-5;
int main() {
int m,n,ans,cnt;
while(scanf("%d%d",&n,&m)!=EOF) {
if(m<n) {
printf("-1\n");
continue;
}
ans=cnt=0;
ans+=n-1;
k=m-n+1-eps;
for(int i=1;i<=n;i++)
a[i]=n*1.0/i;
for(int i=1;i<=n;i++){
cnt=k/a[i];
k-=cnt*a[i];
ans+=cnt;
}
cout<<ans<<endl;
}
return 0;
}