# 51 条题解

• @ 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;
}
``````
• @ 2018-08-29 12:59:28

模拟退火真是个好东西。。。

``````#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;
}
``````
• @ 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. ```

• @ 2013-12-08 16:15:03

简单的加权中位数。可以分别将x，y数组排序以后，分别找x，y的加权中位数。z就是p*k，就是权值。排序后，O（n）的扫描累加，t += z[i],当t>tot /t (tot为总权值)，x[i]就是ansx；y同理。
详细题解和程序见：题解

• @ 2014-10-21 15:37:28

非常感谢你的结论 但我想不通的是为什么非要t>tot时是加权中位数呢 求大神解释

• @ 2014-10-21 15:49:42

我想问的是t>tot/t 刚刚打错了

• @ 2014-10-21 15:57:33

主要是大神你题解里的代码是t>=tot/2 按了你的改我就AC了 所以想问清楚

• @ 2013-02-16 10:15:20
• @ 2012-10-28 16:23:07

编译通过...

├ 测试数据 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()

for(i=1;;i++)

break;}

return city[i].x;

}

int searchy()

for(i=1;;i++)

break;}

return city[i].y;

}

int main()

{scanf("%d\n",&n);

int i;

for(i=1;i

• @ 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

• @ 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了。。。。

• @ 2016-07-03 23:19:55

别装B了

• @ 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！！

• @ 2016-07-03 23:19:34

别装B了

• @ 2009-10-24 21:38:32

“不一定要在城市上”不然20分

• @ 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 的 （貌似排序 没那么快）

• @ 2018-05-20 20:22:26

别装B了

• @ 2009-10-22 18:19:45

令c(i)表示I到Ans的X坐标的权。

d(i)表示I到Ans的Y坐标的权。

答案的X坐标I必定满足：

令a=sigma(c(j)) | 点jX坐标i

则a=b（否则I+1或I-1必定更优秀）

答案的Y坐标同理。

并且只要满足上述两个条件，一定就是答案的X坐标/Y坐标。

所以排序下扫描即可。

• @ 2009-10-05 13:13:37

....long long啊！

找了半天没找出来哪儿错了。。。T_T

后来的朋友注意啊！

• @ 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)呜呜

• @ 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

终于过了

• @ 2009-09-10 19:56:13

虽是ac了

可还是有疑问 数学太沙茶了……

• @ 2009-09-04 18:03:07

用iostream读入会大大超时

• @ 2018-05-20 20:22:47

确实是这样

• @ 2009-08-26 17:28:52

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

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

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

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

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

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

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

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

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

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

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

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

...用int64是正确的

• @ 2009-08-10 13:21:05

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

爽! 一次AC。

• @ 2009-07-27 20:40:20

编译通过...

├ 测试数据 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]排排坐，求中位数

ID
1036

5

(无)

1152

420

36%

6