题解

51 条题解

  • 3
    @ 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
    @ 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;
    }
    
  • 1
    @ 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
    @ 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了 所以想问清楚

  • 0
    @ 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()

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

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

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

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

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

  • 0
    @ 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坐标。

    所以排序下扫描即可。

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

    ....long long啊!

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

    后来的朋友注意啊!

  • 0
    @ 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
    @ 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
    @ 2009-09-10 19:56:13

    虽是ac了

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

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

    用iostream读入会大大超时

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

      确实是这样

  • 0
    @ 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是正确的

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

  • 0
    @ 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
上传者