2014-01-12

CodeForces 381B Sereja and Stairs——贪心

From CodeForces Contests #223 Div. 2 Problem B

话说这次CF两道水题啊。。。可惜没有把握好机会。

按照这样的趋势，我已经预感到了我的排名会继续往下掉，直到无尽的灰色。。。。。

感觉这题是Special Judge的（←所以我连最后的空格都没删）。。。。我觉得我完全没读懂题目是如何要求最后输出的就根据题目要求做了几个字符串输出居然就AC了。。。

方法更是简单粗暴：先排个序，然后建一张表，把数组中的数字当作键名，出现次数作为值。然后按照键名从大到小输出两次，分别存入两个表里。

然后判断顶部是不是相同，如果相同就弹掉一个。

然后把其中一个表倒序。两个表合并。输出。

如果使用C++来写这题，用和我相同的方法可以使用STL的map容器。map容器是自动按照键名从小到大排序的，所以并不需要处理排序的问题。

<?php 
//处理输入 
$in=fgets(STDIN); 
$in=intval($in); 
$str=fgets(STDIN); 
$arr=explode(" ", $str); 
foreach ($arr as &$va) { 
    $va=intval($va); 
} 

//倒序排列$arr数组 
rsort($arr); 

//根据$arr整理出表（←表的含义如上分析） 
$ans=array(); 
foreach($arr as $v){ 
    if(empty($ans[$v])){ 
        $ans+=array($v=>1); 
    }else{ 
        $ans[$v]++; 
    } 
} 

//把每个不同的元素输出，第一次。 
$i=0; 
$tar=array(); 
foreach ($ans as $k=>&$v) { 
    if($v!=0){ 
        $tar[$i]=$k; 
        $v--; 
        $i++; 
    } 
} 

//把每个不同的元素输出，第二次。注意如果某个值已经为0，则不输出。 
$i=0; 
$car=array(); 
foreach ($ans as $k=>&$v) { 
    if($v!=0){ 
        $car[$i]=$k; 
        $v--; 
        $i++; 
    } 
} 
//$arr中剩下的值都是我们不需要的，我们只需要这两次输出的元素就可以构造出符合题意的解。 

//判断两次输出顶部元素是否相同，如果相同就弹出其中一个。 
if($tar[0]==$car[0]) unset($tar[0]); 
//反序其中一个输出，因为我是从大到小排列的，所以这个反序后的数组将会排到前面。 
$car=array_reverse($car); 

//根据题意构造输出。 
$num=count($tar)+count($car); 
echo $num."n"; 
foreach ($car as $v) { 
    echo $v." "; 
} 
foreach ($tar as $v) { 
    echo $v." "; 
} 

?> 

main