首页 > > 程序设计 > C/C++ >

POJ1862 Stripies 贪心 B

2018-12-04 07:15:35来源：博客园阅读 ()

POJ 1862 Stripies

https://vjudge.net/problem/POJ-1862

题目：

Our chemical biologists have invented a new very useful form of life called stripies (in fact, they were first called in Russian - polosatiki, but the scientists had to invent an English name to apply for an international patent). The stripies are transparent amorphous amebiform creatures that live in flat colonies in a jelly-like nutrient medium. Most of the time the stripies are moving. When two of them collide a new stripie appears instead of them. Long observations made by our scientists enabled them to establish that the weight of the new stripie isn't equal to the sum of weights of two disappeared stripies that collided; nevertheless, they soon learned that when two stripies of weights m1 and m2 collide the weight of resulting stripie equals to 2*sqrt(m1*m2). Our chemical biologists are very anxious to know to what limits can decrease the total weight of a given colony of stripies.
You are to write a program that will help them to answer this question. You may assume that 3 or more stipies never collide together.

Input

The first line of the input contains one integer N (1 <= N <= 100) - the number of stripies in a colony. Each of next N lines contains one integer ranging from 1 to 10000 - the weight of the corresponding stripie.

Output

The output must contain one line with the minimal possible total weight of colony with the accuracy of three decimal digits after the point.

Sample Input

Sample Output

120.000

分析：

贪心题目

题目本身不难，总共就几种策略，WA几发蒙也能蒙过了

问题在于这个题为什么这么做是正确的

我在做的时候就顺便用txt进行了证明，毕竟是练习，也为了保证一遍过

首先写了这个，然后意识到不是相加，是直接把v1和v2变成另外一种，所以这是错误的

然后列了几种情况，当两个数的时候，产生的结果是不固定的，可能大，可能小，也可能与其中一个相等，这里就可以想到用增加变量然后用字母来代替数值进行分析

V1v2v3

然后进行第一步，如果12合并，如果23合并，如果13合并

一行一个情况

在这其中保证

那么最后的三个结果就是

看起来比较复杂emmmm

那就简单化简吧，假设第一个和第二个相等

化简

然后取平方

诶是不是发现什么了

都会有

这个东西，

唯一的区别是v1,v2,v3

那么显然是

倒推：

得证

放全部分析过程：

v1+v2 -> 2*sqrt(v1*v2)

sqrt(v1^2+v2^2+2*v1*v2) -> sqrt(4*v1*v2)

1 100

72 50

120

2 50

5 20

v1 v2 v3

2*sqrt(v1*v2) v3

2*sqrt(v1*v3) v2

2*sqrt(v2*v3) v1

v1<v2<v3

2*sqrt(2*sqrt(v1*v2)*v3)

2*sqrt(2*sqrt(v1*v3)*v2)

2*sqrt(2*sqrt(v2*v3)*v1)

2*sqrt(2*sqrt(v1*v2)*v3)=2*sqrt(2*sqrt(v1*v3)*v2)

sqrt(v1*v3)*v2=sqrt(v1*v2)*v3

v1*v2*v3*v3 v1*v3*v2*v2

v1*v2*v3

v1*v2*v3*v1 min

也就是sqrt(v2*v3)*v1

再倒推就是2*sqrt(2*sqrt(v2*v3)*v1)

再倒推就是先处理两个大的

得证

AC代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <string>
 7 #include <time.h>
 8 #include <queue>
 9 #include <string.h>
10 #define sf scanf
11 #define pf printf
12 #define lf double
13 #define ll long long
14 #define p123 printf("123\n");
15 #define pn printf("\n");
16 #define pk printf(" ");
17 #define p(n) printf("%d",n);
18 #define pln(n) printf("%d\n",n);
19 #define s(n) scanf("%d",&n);
20 #define ss(n) scanf("%s",n);
21 #define ps(n) printf("%s",n);
22 #define sld(n) scanf("%lld",&n);
23 #define pld(n) printf("%lld",n);
24 #define slf(n) scanf("%lf",&n);
25 #define plf(n) printf("%lf",n);
26 #define sc(n) scanf("%c",&n);
27 #define pc(n) printf("%c",n);
28 #define gc getchar();
29 #define re(n,a) memset(n,a,sizeof(n));
30 #define len(a) strlen(a)
31 #define LL long long
32 #define eps 1e-6
33 using namespace std;
34 double a[100500];
35 bool cmp(double a, double b){
36     return a > b;
37 }
38 int main() {
39     int n = 0;
40     s(n);
41     for(int i = 0; i < n; i ++){
42         slf(a[i]);
43     }
44     sort(a,a+n,cmp);
45     double temp = a[0];
46     for(int i = 1; i< n ;i ++){
47         temp = 2.0*sqrt(a[i]*temp);
48     }
49     pf("%.3lf\n",temp);
50     return 0;
51 }