第五届新疆省ACM-ICPC程序设计竞赛(重现赛)D - O(n!)(贪心)

题目

链接:https://ac.nowcoder.com/acm/contest/911/D
来源:牛客网

有 n件商品,第 i件商品价格为 a[i],购买后,其它所有未购买的商品价格乘上 p[i],现在要买下所有商品,输出最小耗费。
输入描述:
第一行一个整数 n(n≤105),接下来 n 行,第 i 行两个数字a[i],p[i],其中 a[i] 为整数,p[i] 为浮点数,
1≤a[i]≤105,0≤p[i]≤1。
输出描述:保留六位小数输出。
示例1
输入

1
2
3
2
1 0.5
10 1

输出

1
6.000000

示例2
输入

1
2
3
4
3
27545 0.79
77924 0.1
64441 0.66

输出

1
85769.339000

备注:

  • 样例 1:先买 1 号商品,再买 2 号商品。
  • 样例 2:先买 2 号商品,再买 1 号,最后买 3 号。

思路

首先对于两个物品,有物品1(v1,p1),物品2(v2,p2);
先取第一个物品:ans1=v1+p1v2;
先取第二个物品:ans2=v2+p2
v1;

要使得ans1<ans2,则有v1+p1v2<v2+p2v1,
化简后:v1/(1-p1)<v2/(1-p2)

对于两个物品是如此,三个乃至更多的物品就是从局部解推及到最优解。

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
https://ac.nowcoder.com/acm/contest/911/D
AC
*/
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;

struct node {
double value;
double price;
double x;
};

node arr[MAXN];

bool cmp(node a,node b){
return a.x<b.x;
}
int main() {
int N;
scanf("%d",&N);

for(int i=1;i<=N;i++) {
scanf("%lf%lf",&arr[i].value,&arr[i].price);
arr[i].x=arr[i].value/(1-arr[i].price);
}

sort(arr+1,arr+N+1,cmp);

// for(int i=1;i<=N;i++)
// cout<<arr[i].value<<' '<<arr[i].price<<' '<<arr[i].x<<endl;
long double sum=0;
long double p=1.0;
for(int i=1;i<=N;i++) {
sum+=arr[i].value*p;
p*=arr[i].price;
}
printf("%.6Lf\n",sum);
return 0;
}
-------------本文结束感谢您的阅读-------------
0%