The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Topcoder 463 Div 2 1000

Problem Statement

     Taro and Hanako are playing a game called Nisoku, which is played as follows. Initially, there is a pile of cards. Each card contains a real number between 1.5 and 10.0, inclusive. You are given a vector <double> cards, the i-th element of which is the number written on the i-th card.

Repeat the following step until there is only one card left in the pile: Remove any two cards from the pile, and add one new card to the pile. Write either a+b or a*b on the new card, where a and b are the numbers written on the two cards that were removed.

Return the maximal possible number written on the final card in the pile.

Definition

    
Class: Nisoku
Method: theMax
Parameters: vector <double>
Returns: double
Method signature: double theMax(vector <double> cards)
(be sure your method is public)
    

Notes

- Your return value must have an absolute or relative error less than 1e-9.

Constraints

- cards will contain between 2 and 50 elements, inclusive.
- Each element of cards will be between 1.5 and 10.0, inclusive.

Examples

0)
    
{5, 8}
Returns: 40.0
5 * 8 = 40.
1)
    
{1.5, 1.8}
Returns: 3.3
1.5 + 1.8 = 3.3.
2)
    
{8.26, 7.54, 3.2567}
Returns: 202.82857868
3)
    
{1.5, 1.7, 1.6, 1.5}
Returns: 9.920000000000002
4)
    
{10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10}
Returns: 1.0E50
The answer can be extremely big.




发现偶还是太水了。。。

#include<iostream>
#include
<algorithm>
#include
<vector>
using namespace std;



class Nisoku
{
public:
    
double theMax(vector<double>cards)
    
{    
        
int i,j;
        sort(cards.begin(),cards.end());
        
double ans=0;
        
for(i=0;i<=cards.size();i+=2)
        
{
            
double p=1;
            
for(j=0;j<i/2;j++)
                p
*=(cards[j]+cards[i-1-j]);
            
for(j=i;j<cards.size();j++)
                p
*=cards[j];
            ans
=max(ans,p);
        }

        
return ans;
    }

}
;

谁能证明下这份代码的正确性?

posted on 2010-03-02 22:27 abilitytao 阅读(988) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理