题目大意：
若在x处防止一个覆盖范围为r的wifi基站
可以覆盖 x-r 到 x+r 范围 花费为 A+B*r
给定n 给定n个奶牛的位置
求覆盖所有奶牛的最小费用 （可设置任意多个wifi基站）
贪心 对于连续的一段奶牛只设一个wifi
当发现 将一头奶牛加进来时 多设一个wifi比起仍然用一个wifi更优
就从下一头奶牛开始 设另一个wifi
double型运算可能存在误差
由于在一段区间中设置一个wifi时 设置位置为中间最优
故 花费 = A + B * ( l / 2 ) 则变为 2 * 花费 = 2 * A + B * l
就可以直接用int型计算了 最后得到的答案除二就行
#include <bits/stdc++.h> using namespace std; #define LL long long #define INF 0x3f3f3f3f #define mem(i,j) memset(i,j,sizeof(i)) #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,r,l) for(int i=r;i>=l;i--) const int N=2000+5; const int mod=1e9+7; const int eps=1e-8; int n; LL A,B,a[N]; int main() { while(~scanf("%d%lld%lld",&n,&A,&B)) { inc(i,1,n) scanf("%lld",&a[i]); sort(a+1,a+1+n); LL ans=0; int i=1; while(i<=n) { int j=i+1; LL t=2LL*A; while(j<=n) { LL ans1=(a[j]-a[i])*B+2LL*A; LL ans2=t+2LL*A; if(ans1>ans2) break; t=ans1; j++; } ans+=t; i=j; } if(ans%2LL) printf("%lld.5\n",ans/2LL); else printf("%lld\n",ans/2LL); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/10546517.html
