/ Vijos / 题库 / 拯救世界-紧急召集 /

题解

55 条题解

  • 2
    @ 2016-09-08 01:37:40

    #include <iostream>
    #include <string>
    #include <cmath>

    using namespace std;

    double nationp[5000];//科研人数
    double nationx[5000];//距离
    string nationn[5000];//名字

    double money[5000];//花费

    double ans[5000];//归并排序储存花费数组
    string anss[5000];// 归并排序储存名字数组

    void gb_sort( int l, int r)
    {
    if(l==r)return;//只有一个不需排序
    int mid=(l+r)/2;//从中间分为两个有序列
    gb_sort( l, mid);//对左边的排序
    gb_sort( mid+1, r);//对右边的排序
    int k=l; //一次归并
    int i=l;
    int j=mid+1;
    while(i<=mid&&j<=r)
    {
    if(money[i]<money[j])
    {
    ans[k]=money[i];
    anss[k]=nationn[i];
    ++i;
    ++k;
    }else
    {
    ans[k]=money[j];
    anss[k]=nationn[j];
    ++j;
    ++k;
    }
    }
    while(i<=mid) //导入剩余项
    {

    ans[k]=money[i];
    anss[k]=nationn[i];
    ++i;
    ++k;
    }
    while(j<=r)
    {
    ans[k]=money[j];
    anss[k]=nationn[j];
    ++j;
    ++k;
    }
    for(k=l;k<=r;++k) //输出有序列
    {
    money[k]=ans[k];
    nationn[k]=anss[k];
    }
    return;
    }

    int main()
    {
    ios::sync_with_stdio(false);
    int i;
    int num=0;
    while(cin>>nationp[num])//输入
    {
    cin>>nationx[num];
    cin>>nationn[num];
    for(i=0;i<num;++i)//算花费
    {
    double c=abs(nationx[i]-nationx[num]);
    money[i]+=c*nationp[num];//往后算
    money[num]+=c*nationp[i];//往前算
    }
    ++num;
    }
    gb_sort(0,num-1);
    cout<<nationn[0];
    return 0;
    }

  • 1
    @ 2023-06-06 20:33:50 
    #include <iostream>
#include <string>
#include <cmath>

using namespace std;

double nationp[5000];//科研人数
double nationx[5000];//距离
string nationn[5000];//名字

double money[5000];//花费

double ans[5000];//归并排序储存花费数组
string anss[5000];// 归并排序储存名字数组

void gb_sort( int l, int r)
{
if(l==r)return;//只有一个不需排序
int mid=(l+r)/2;//从中间分为两个有序列
gb_sort( l, mid);//对左边的排序
gb_sort( mid+1, r);//对右边的排序
int k=l; //一次归并
int i=l;
int j=mid+1;
while(i<=mid&&j<=r)
{
if(money[i]<money[j])
{
ans[k]=money[i];
anss[k]=nationn[i];
++i;
++k;
}else
{
ans[k]=money[j];
anss[k]=nationn[j];
++j;
++k;
}
}
while(i<=mid) //导入剩余项
{

ans[k]=money[i];
anss[k]=nationn[i];
++i;
++k;
}
while(j<=r)
{
ans[k]=money[j];
anss[k]=nationn[j];
++j;
++k;
}
for(k=l;k<=r;++k) //输出有序列
{
money[k]=ans[k];
nationn[k]=anss[k];
}
return;
}

int main()
{
ios::sync_with_stdio(false);
int i;
int num=0;
while(cin>>nationp[num])//输入
{
cin>>nationx[num];
cin>>nationn[num];
for(i=0;i<num;++i)//算花费
{
double c=abs(nationx[i]-nationx[num]);
money[i]+=c*nationp[num];//往后算
money[num]+=c*nationp[i];//往前算
}
++num;
}
gb_sort(0,num-1);
cout<<nationn[0];
return 0;
}
  • 1
    @ 2016-07-08 18:04:47

    U43
    pascal
    var
    ch:char;
    s,minr:double;
    i,j,n,mini:longint;
    man,dist:array[1..10000]of double;
    country:array[1..5000]of ansistring;
    begin
    n:=0;
    while not eof do
    begin
    inc(n);
    readln(man[n],dist[n],ch,country[n]);
    end;
    minr:=sqr(maxlongint); //注意啦注意啦注意啦，如果是maxlongint的话错最后3个点！！！！！
    for i:=1 to n do
    begin
    s:=0;
    for j:=1 to n do s:=s+man[j]*abs(dist[i]-dist[j]);
    if minr>s then
    begin
    minr:=s;
    mini:=i;
    end;
    end;
    write(country[mini]);
    end.

  • 0
    @ 2016-09-08 01:36:45

    我去，快排后三个超时，换了个归并才搞定，long long int居然在后三个输出错误，必须用double，这数据有毒啊
    #include <iostream>
    #include <string>
    #include <cmath>

    using namespace std;

    double nationp[5000];//科研人数
    double nationx[5000];//距离
    string nationn[5000];//名字

    double money[5000];//花费

    double ans[5000];//归并排序储存花费数组
    string anss[5000];// 归并排序储存名字数组

    void gb_sort( int l, int r)
    {
    if(l==r)return;//只有一个不需排序
    int mid=(l+r)/2;//从中间分为两个有序列
    gb_sort( l, mid);//对左边的排序
    gb_sort( mid+1, r);//对右边的排序
    int k=l; //一次归并
    int i=l;
    int j=mid+1;
    while(i<=mid&&j<=r)
    {
    if(money[i]<money[j])
    {
    ans[k]=money[i];
    anss[k]=nationn[i];
    ++i;
    ++k;
    }else
    {
    ans[k]=money[j];
    anss[k]=nationn[j];
    ++j;
    ++k;
    }
    }
    while(i<=mid) //导入剩余项
    {

    ans[k]=money[i];
    anss[k]=nationn[i];
    ++i;
    ++k;
    }
    while(j<=r)
    {
    ans[k]=money[j];
    anss[k]=nationn[j];
    ++j;
    ++k;
    }
    for(k=l;k<=r;++k) //输出有序列
    {
    money[k]=ans[k];
    nationn[k]=anss[k];
    }
    return;
    }

    int main()
    {
    ios::sync_with_stdio(false);
    int i;
    int num=0;
    while(cin>>nationp[num])//输入
    {
    cin>>nationx[num];
    cin>>nationn[num];
    for(i=0;i<num;++i)//算花费
    {
    double c=abs(nationx[i]-nationx[num]);
    money[i]+=c*nationp[num];//往后算
    money[num]+=c*nationp[i];//往前算
    }
    ++num;
    }
    gb_sort(0,num-1);
    cout<<nationn[0];
    return 0;
    }

  • 0
    @ 2016-07-10 10:30:24

    U43
    还有一种O（n）的做法：
    pascal
    type
    arr=array[0..5001]of double;
    var
    ch:char;
    total,sum:double;
    i,n:longint;
    man,dist:arr;
    country:array[1..5000]of ansistring;
    procedure qsort(var a:arr;l,r:longint);
    var
    i,j:longint;
    tmp,mid:double;
    tmp2:ansistring;
    begin
    i:=l;j:=r;
    mid:=a[(i+j) div 2];
    repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
    begin
    tmp:=a[i];a[i]:=a[j];a[j]:=tmp;
    tmp:=man[i];man[i]:=man[j];man[j]:=tmp;
    tmp2:=country[i];country[i]:=country[j];country[j]:=tmp2;
    inc(i);dec(j);
    end;
    until i>j;
    if l<j then qsort(a,l,j);
    if i<r then qsort(a,i,r);
    end;
    begin
    n:=0;
    total:=0;
    while not eof do
    begin
    inc(n);
    readln(man[n],dist[n],ch,country[n]);
    total:=total+man[n];
    end;
    qsort(dist,1,n);
    sum:=0;
    for i:=1 to n do
    begin
    sum:=sum+man[i];
    if sum>total/2 then break;
    end;
    write(country[i]);
    end.

  • 0
    @ 2012-08-01 21:34:10

    大家不要想复杂了,因为n

  • 0
    @ 2009-11-10 09:29:57

    Orz 楼下

  • 0
    @ 2009-11-10 09:07:47

    坐标是Double……人数为什么不会是Double……

  • 0
    @ 2009-11-09 09:31:43

    水题....

    o(n)的算法；

    数据要用double啊......切记切记，我用int64还WA了....

  • 0
    @ 2009-11-02 08:49:57

    最后3个点运行超时/无输出的看这里：

    最大值用maxlongint不够！要用sqr(maxlongint)!!!!!

    解法转载tanconghui神牛.....

    ---|---|---|---|---|---|---|---|---|---|--

    O(NlgN+N)的算法，先排序，再递推：

    设dis[i]为从我国到i国的距离，lp[i]为在i国左边的国家的科学家总人数（即dis[j]

  • 0
    @ 2009-10-20 12:10:06

    采用物理的力矩！！！进行剪枝！！！

    理论上讲，算出来的结果就是确切的值，但是不知为什么wa了...

    然后扩大搜索范围....0ms,AC

    ...............

    ---|---|---|---|---|---|---|---|---|---|---|-

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    var l:longint;p:array[0..5000]of longint;

    dis:array[0..5000]of real;

    name:array[0..5000]of string[20];

    procedure init;

    var ch:char;

    begin

    l:=0;

    while not(eof) do

    begin

    inc(l);

    readln(p[l],dis[l],ch,name[l]);

    end;

    end;

    procedure qsort(l,r:longint);

    var i,j:longint;s:string;z:longint;x,t:real;

    begin

    i:=l;j:=r;

    x:=dis[(i+j) shr 1];

    repeat

    while dis[i]x do dec(j);

    if ij;

    if l

  • 0
    @ 2009-10-13 19:04:47

    跟1036一样哦

  • 0
    @ 2009-10-11 14:52:34

    Double+模拟 还加了个几乎没用的剪枝 直接秒掉

    为什么我用extended会TLE3个点呢 还是运行超时|无输出

    无语的第199个

  • 0
    @ 2009-09-06 17:31:23

    为什么楼下大牛说是实型、、？？我没有注意就用的int64列。。。。。

    还有我觉得排序后，若i点前人数超过了一半就直接输出i的名字咯。。。

  • 0
    @ 2009-08-28 13:26:13

    Double 模拟

  • 0
    @ 2009-08-27 23:07:59

    居然没说是整形~，，还No Compiled了1次，。，。

  • 0
    @ 2009-08-21 22:07:54

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    代码已加防作弊，请以学习的态度对待，请勿直接抄袭！！！

    #include

    #include

    #include

    using namespace std;

    int main()

    {

    double x,s,minr,ren[10000],ju[10000];

    string guo[10000];

    long n=0;

    long long mini,i,j;

    while(scanf("%lf",&x)!=EOF)

    {

    n++;

    ren[n]=x;

    cin >> ju[n] >> guo[n];

    }

    minr=1;

    for(i=1;i

  • 0
    @ 2009-08-13 20:14:52

    实数！

    O(n)瞬秒！

  • 0
    @ 2009-08-11 12:31:20

    直接模拟即可，但数据一定要用double类型。

  • 0
    @ 2009-08-01 11:12:18

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    O(NlgN+N)的算法，先排序，再递推：

    设dis[i]为从我国到i国的距离，lp[i]为在i国左边的国家的科学家总人数（即dis[j]

拯救世界-紧急召集

信息

ID
1225
难度
6
分类
高精度 | 其他 | 排序 点击显示
标签
(无)
递交数
1194
已通过
277
通过率
23%
被复制
5
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1