51 条题解
-
4
猫粮寸断 LV 10 @ 2018-09-01 09:49:24
带权中位数问题，并不是很难写
#include<iostream> #include<algorithm> using namespace std; int sum[100010]; struct node { int x,y,p,k; }q[100010]; int cmp1(const node&x,const node&y) { return x.x<y.x; } int cmp2(const node&x,const node&y) { return x.y<y.y; } int main() { int n,i,l,r,m,x,y; cin>>n; for(i=1;i<=n;i++) cin>>q[i].x>>q[i].y>>q[i].p>>q[i].k; sort(q+1,q+n+1,cmp1); for(i=1;i<=n;i++) sum[i]=sum[i-1]+q[i].p*q[i].k; for(i=1;i<=n;i++) { if(sum[i]>=sum[n]-sum[i]&&sum[i-1]<=sum[n]-sum[i-1]) break; } x=q[i].x; sort(q+1,q+n+1,cmp2); for(i=1;i<=n;i++) sum[i]=sum[i-1]+q[i].p*q[i].k; for(i=1;i<=n;i++) { if(sum[i]>=sum[n]-sum[i]&&sum[i-1]<=sum[n]-sum[i-1]) break; } y=q[i].y; cout<<x<<" "<<y; return 0; } -
1
模拟退火真是个好东西。。。
#include<bits/stdc++.h> #define i64 long long using namespace std; i64 n; i64 x[100001],y[100001],w[100001],p,k; i64 i64abs (i64 X) { if (X<0) return -X; else return X; } i64 calc (i64 xx,i64 yy) { i64 sum=0; for (i64 i=1;i<=n;i++) sum+=(i64)w[i]*(i64abs(x[i]-xx)+i64abs(y[i]-yy)); return sum; } i64 ansx,ansy,nx,ny,tx,ty; double step; i64 ans; double C=0.99; double pi=acos(-1.0); double theta; i64 lx,rx,ly,ry; void update (i64 p,i64 q,i64 f) { ans=p; ansx=q; ansy=f; return; } bool P (double p) { if (p>=1) return true; p*=10000; int gailv=(p+0.000001); int suiji=rand()%10000; if (suiji>gailv-1) return false; else return true; } int main() { srand(time(0)); scanf("%lld",&n); lx=9223372036854775807; rx=-9223372036854775807; ly=9223372036854775807; ry=-9223372036854775807; for (i64 i=1;i<=n;i++) { scanf("%lld%lld%lld%lld",&x[i],&y[i],&p,&k); w[i]=p*k; //printf("%lld\n",w[i]); lx=min(lx,x[i]); rx=max(rx,x[i]); ly=min(ly,y[i]); ry=max(ry,y[i]); } nx=ansx=(lx+rx)>>1; ny=ansy=(ly+ry)>>1; ans=calc(nx,ny); step=2000000000; //printf("%lld %lld\n",calc(6,3),calc(4,3)); while (step>=0.5) { theta=rand()%360; theta/=180.0; theta*=pi; tx=int(nx+step*cos(theta)+0.5); ty=int(ny+step*sin(theta)+0.5); if (tx<0) tx+=9223372036854775807; if (ty<0) ty+=9223372036854775807; tx=((tx-lx)%(rx-lx+1)+rx-lx+1)%(rx-lx+1)+lx; ty=((ty-ly)%(ry-ly+1)+ry-ly+1)%(ry-ly+1)+ly; i64 num=calc(tx,ty); //printf("now(%lld,%lld) ans(%lld,%lld)=%lld rand(%lld,%lld)=%lld\n",nx,ny,ansx,ansy,ans,tx,ty,num); if (P(pow(exp(1),(ans-num)*1.0/(step/3.0)))) nx=tx,ny=ty; if (num<ans) update(num,tx,ty); else if (num==ans && tx<ansx) update(num,tx,ty); else if (num==ans && tx==ansx && ty<ansy) update(num,tx,ty); step*=C; } printf("%lld %lld\n",ansx,ansy); return 0; } -
1
正在加载...99% LV 8 @ 2016-07-08 18:23:54
U43
带权中位数（权为p*k）
和 http://wenda.so.com/q/1437840779616335 （超级篮球赛）是一个类型的，不过此题更简单。
pascal
type
arr=array[0..100001] of longint;
var
i,p,k,n,tx,ty:longint;
total:double;
x,y,v,oldv:arr;
procedure qsort(var a:arr;l,r:longint);
var
i,j,mid,tmp:longint;
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:=v[i];v[i]:=v[j];v[j]:=tmp;
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;
function workx:longint;
var
i:longint;
sum:double;
begin
sum:=0;
for i:=1 to n do
begin
sum:=sum+v[i];
if sum>total/2 then exit(x[i]);
end;
end;
function worky:longint;
var
i:longint;
sum:double;
begin
sum:=0;
for i:=1 to n do
begin
sum:=sum+v[i];
if sum>total/2 then exit(y[i]);
end;
end;
begin
total:=0;
read(n);
for i:=1 to n do
begin
read(x[i],y[i],p,k);
v[i]:=p*k;
total:=total+v[i];
end;
oldv:=v;
qsort(x,1,n);
tx:=workx;
v:=oldv; //这一步万万不能忘，因为之前的排序已经打乱了v数组的顺序
qsort(y,1,n);
ty:=worky;
write(tx,' ',ty);
end.
-
0
简单的加权中位数。可以分别将x，y数组排序以后，分别找x，y的加权中位数。z就是p*k，就是权值。排序后，O（n）的扫描累加，t += z[i],当t>tot /t (tot为总权值)，x[i]就是ansx；y同理。
详细题解和程序见：题解 -
0
-
0
编译通过...
├ 测试数据 01：答案正确... (0ms, 2532KB)
├ 测试数据 02：答案正确... (0ms, 2532KB)
├ 测试数据 03：答案正确... (0ms, 2532KB)
├ 测试数据 04：答案正确... (0ms, 2532KB)
├ 测试数据 05：答案正确... (0ms, 2532KB)
├ 测试数据 06：答案正确... (0ms, 2532KB)
├ 测试数据 07：答案正确... (0ms, 2532KB)
├ 测试数据 08：答案正确... (0ms, 2532KB)
├ 测试数据 09：答案正确... (28ms, 2532KB)
├ 测试数据 10：答案正确... (59ms, 2532KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 88ms / 2532KB
C语言二级排序,正交分解求带权中位数的程序凑合看吧#include
#include
struct map
{int x;
int y;
int p;
int k;
long long value;}city[100001];
int n,ex,ey,sum=0;
int cmp1(const void*a,const void *b)
{struct map*c=(struct map*)a;
struct map*d=(struct map*)b;
if(c->x!=d->x)return c->x-d->x;
else
return c->y-d->y;
}int cmp2(const void*a,const void *b)
{struct map*c=(struct map*)a;
struct map*d=(struct map*)b;
if(c->y!=d->y)return c->y-d->y;
else
return c->x-d->x;
}int searchx()
{int i,add=0;
for(i=1;;i++)
{add+=city[i].value;
if(add>=sum/2)
break;}
return city[i].x;
}int searchy()
{int i,add=0;
for(i=1;;i++)
{add+=city[i].value;
if(add>=sum/2)
break;}
return city[i].y;
}int main()
{scanf("%d\n",&n);
int i;
for(i=1;i -
0
liumengyun LV 8 @ 2010-04-01 22:11:29
不知道有没有人写过，懒得翻了。
讲一个o(n)的算法吧。其实就是加权中位数的o（n）算法。
答案的满足条件
我就不详细证了，简单写一下，就是设i左边的权值总和为s(i),所有结点的权值和为sum.当s[i]*2-sum=0。此时i+1即为答案。i到i+1权值的变化量为s[i]*l-(sum-s[i])*l=l*(s[i]*2-sum).
然后用一个qsort的模块{类似中位数的o（n）算法）
function qsorta(x,y,k:longint):longint;//k为此时x左边权值和(不包括x)
var sum,s1,s2,t,i,j:longint;
begin
if x -
0
mintalfance LV 10 @ 2009-11-03 14:37:41
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms终于A了。。。。
-
hfctf0210 @ 2016-07-03 23:19:55
别装B了
-
-
0
qaz674235205 LV 7 @ 2009-10-30 22:14:30
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
哇，全部0ms！！-
别装B了
-
-
0
youandmetz LV 8 @ 2009-10-24 11:04:11
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 56ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：128ms有没有人 提供一下 0ms 的 （貌似排序 没那么快）
-
YG666 @ 2018-05-20 20:22:26
别装B了
-
-
0
prince_hao LV 10 @ 2009-10-01 18:25:26
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 25ms
├ 测试数据 10：答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：50ms竟然没有一次AC呜呜呜呜
写第二个排序的时候直接把第一个排序的代码复制了
结果里面递归调用的代码忘记改了！
把QSORT1(I,R)写成了QSORT(I,R)呜呜 -
0
zhanghanyuan LV 10 @ 2009-09-21 21:10:25
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 25ms
├ 测试数据 09：答案正确... 25ms
├ 测试数据 10：答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：122ms
终于过了 -
0
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 25ms
├ 测试数据 10：答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：97ms
...用int64是正确的 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 56ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：65ms
爽! 一次AC。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 41ms
├ 测试数据 09：答案正确... 41ms
├ 测试数据 10：答案正确... 119ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：210ms
所谓带权中位数，就是给定的N个数都有一个权值，或者说相当于个数。此时的中位数就不再是第(N div 2)个数了，而是第((w[1]+w[2]+...w[i])div 2)个数。w[i]表示排序后第i个数的权~~
再简单来讲就是w[i]个a[i]排排坐，求中位数
猫粮寸断
LV 10
@ 2018-09-01 09:49:24
