syhd142  
日历
<2024年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
看了解题报告,才知道可以贪心,需要证明,具体见(http://www.algorithmist.com/index.php/UVa_410)
因为精度问题而一直错,所以干脆都乘一个c,最后再除,这样大大减少了误差。
#include <stdio.h>
#include 
<string.h>
#include 
<algorithm>

int a[20];

inline 
int abs(int x)
{
    
if(x > 0return x;
    
return -x;
}

int main()
{
//    freopen("in", "r", stdin);
    int c, s, n, cas = 1;
    
while(~scanf("%d %d"&c, &s))
    {
        memset(a, 
0sizeof(a));
        n 
= (c << 1- s;
        
int ave = 0;
        
for(int i = n; i < (c << 1); i++)
        {
            scanf(
"%d"&a[i]);
            ave 
+= a[i];
        }
    
//    printf("ave = %lf\n", ave);
        std::sort(a, a + (c << 1));
        printf(
"Set #%d\n", cas++);
        
double sum = 0;
        
for(int i = 0; i < c; i++)
        {
            printf(
" %d:", i);
            sum 
+= abs(c * a[i] + c * a[(c << 1- i - 1- ave);
            
if(a[i]) printf(" %d", a[i]);
            
if(a[(c << 1- i - 1]) printf(" %d", a[(c << 1- i - 1]);
            printf(
"\n");
        }
        printf(
"IMBALANCE = %.5lf\n\n", sum / c);
    }
    
return 0;
}
posted on 2010-09-20 15:59 Fucker 阅读(468) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC贪心

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © Fucker Powered by: 博客园 模板提供:沪江博客