奶牛的聚会

题目描述

农历新年马上就要到了,奶牛们计划举办一次聚会庆祝新年的到来。但是,奶牛们并不喜欢走太远的路,这会给他们的聚会带来消极情绪,当一头奶牛的消极指数为Wi,他参加聚会所需行走的距离为si,那么他就会给聚会带来Si3*Wi的消极情绪。所有奶牛所在位置都在一条直线上,已知所有奶牛的坐标和消极指数,求如何确定聚会地点,使得所有奶牛给聚会带来的消极情绪之和最小,输出消极情绪之和的最小值。

输入

第一行包含一个整数 Ca(Ca<=20) ,表示有 Ca 组测试数据。

对于每组测试数据:第一行包含一个整数n(1<=n<=50000) ,表示奶牛的数量。接下来 n 行每行包含两个浮点数Si和wi (-106<=Si<=106, 0<Wi<15)。

输出

对于每组测试数据,输出 “Case #c: ans” ,其中c表示测试数据编号,ans表示消极情绪之和的最小值,结果四舍五入为一个整数。

样例输入

1
5
0.9 2
1.4 4
3.1 1
6.2 1
8.3 2

样例输出

Case #1: 300

代码

#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int MAXN = 50010;
const int inf = 0x3fffffff;
const double EPS = 1e-6;
int t,n;
double x[MAXN],w[MAXN];    
 
double chu(double start)       
{
 double sum=0;
 for(int i=0;i<n;i++)
 {
     double d=x[i]-start;
     if(d<0) d=-d;
     sum+=d*d*d*w[i];
 }
 return sum;
}
int main()
{
 cin>>t;
double l,r;
 for(int num=1;num<=t;num++)
 {
  cin>>n;
  l=inf,r=-inf;
  for(int i=0;i<n;i++)
  {
     cin>>x[i]>>w[i];
     if (x[i] > r)
        r= x[i];
    if (x[i] <l)
        l = x[i];
  }
  while(r-l>EPS)            
  {
     double m1=(l+r)/2.0;
     double m2=(m1+r)/2.0;
     if(chu(m1)>chu(m2)) l=m1;
     else r=m2;
  }
 cout<<"Case #"<<num<<": "<< ll(chu(l)+0.5)<<endl;
 }
 return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
简历当中有水分算不算造假...
点赞 评论 收藏
分享
05-24 14:12
门头沟学院 Java
点赞 评论 收藏
分享
06-11 17:39
门头沟学院 Java
小呆呆的大鼻涕:卧槽,用户彻底怒了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务