55 条题解
-
2HBat LV 8 @ 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;
} -
12023-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; }
-
12016-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.
-
02016-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;
} -
02016-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.
-
02012-08-01 21:34:10@
大家不要想复杂了,因为n
-
02009-11-10 09:29:57@
Orz 楼下
-
02009-11-10 09:07:47@
坐标是Double……人数为什么不会是Double……
-
02009-11-09 09:31:43@
水题....
o(n)的算法;
数据要用double啊......切记切记,我用int64还WA了.... -
02009-11-02 08:49:57@
最后3个点运行超时/无输出的看这里:
最大值用maxlongint不够!要用sqr(maxlongint)!!!!!
解法转载tanconghui神牛.....
---|---|---|---|---|---|---|---|---|---|--
O(NlgN+N)的算法,先排序,再递推:
设dis[i]为从我国到i国的距离,lp[i]为在i国左边的国家的科学家总人数(即dis[j] -
02009-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 有效耗时:0msvar 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 -
02009-10-13 19:04:47@
跟1036一样哦
-
02009-10-11 14:52:34@
Double+模拟 还加了个几乎没用的剪枝 直接秒掉
为什么我用extended会TLE3个点呢 还是运行超时|无输出
无语的第199个 -
02009-09-06 17:31:23@
为什么楼下大牛说是实型、、??我没有注意就用的int64列。。。。。
还有我觉得排序后,若i点前人数超过了一半就直接输出i的名字咯。。。
-
02009-08-28 13:26:13@
Double 模拟
-
02009-08-27 23:07:59@
居然没说是整形~,,还No Compiled了1次,。,。
-
02009-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 -
02009-08-13 20:14:52@
实数!
O(n)瞬秒! -
02009-08-11 12:31:20@
直接模拟即可,但数据一定要用double类型。
-
02009-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 有效耗时:0msO(NlgN+N)的算法,先排序,再递推:
设dis[i]为从我国到i国的距离,lp[i]为在i国左边的国家的科学家总人数(即dis[j]