经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
POJ1862 Stripies 贪心 B
来源:cnblogs  作者:Kidgzz  时间:2018/12/3 22:14:08  对本文有异议

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

  1. 3
  2. 72
  3. 30
  4. 50

Sample Output

  1. 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

20

72 50

120

2 50

20

5 20

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

 

 

 

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号