题解

56 条题解

  • 1
    @ 2017-07-27 11:24:28

    排序不等式:逆序和>乱序和>顺序和
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    long long a[100001],b[100001],ans=0,k;
    int main()
    {
    int n;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    int i=1,j=n,l=1,r=n;
    while(i-1+n-j+1<=k)
    {
    if(abs(a[i]-b[r])>abs(a[j]-b[l]))
    {
    ans+=abs(a[i]-b[r]);
    i++;r--;
    }
    else
    {
    ans+=abs(a[j]-b[l]);
    j--;l++;
    }
    }
    cout<<ans;
    return 0;
    }

  • 0
    @ 2020-11-14 18:11:11
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        typedef long long ll;
        
        ll n,t,ans,a[1<<17],b[1<<17],c[1<<17];
        
        int cmp_less(ll x,ll y)
        {
            return x<y;
        }
        int cmp_greater(ll x,ll y)
        {
            return x>y;
        }
        
        void main()
        {
            scanf("%lld%lld",&n,&t);
            for (ll i=0;i<n;i++)
                scanf("%lld",&a[i]);
            for (ll i=0;i<n;i++)
                scanf("%lld",&b[i]);
            sort(&a[0],&a[n],cmp_greater);
            sort(&b[0],&b[n],cmp_less);
            for (ll i=0;i<n;i++)
                c[i]=llabs(a[i]-b[i]);
            sort(&c[0],&c[n],cmp_greater);
            ans=0;
            for (ll i=0;i<t;i++)
                ans+=c[i];
            printf("%lld\n",ans);
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 0
    @ 2017-03-18 10:46:49

    #include <iostream>
    #include <iomanip>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <algorithm>
    using namespace std;
    long long a[100005],b[100005],ans;
    int n,k,i;
    int main()
    {
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
    cin>>a[i];
    }
    for(i=0;i<n;i++)
    {
    cin>>b[i];
    }
    sort(a,a+n);
    sort(b,b+n);
    int i1=0;int i2=0;int j1=n-1;int j2=n-1;
    while(k)
    {
    if(abs(a[i1]-b[j1])>abs(a[j2]-b[i2]))
    {
    ans=ans+abs(a[i1]-b[j1]);
    i1++;j1--;
    }
    else
    {
    ans=ans+abs(a[j2]-b[i2]);
    j2--;i2++;

    }
    k--;
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
    }

  • 0
    @ 2017-02-04 13:12:53

    50AC留念。。。

    #include<stdio.h>
    int a[100000]={0},b[100000]={0};
    void quiksort(int a[],int low,int high)
    {
        int i = low;
        int j = high;  
        int temp = a[i]; 
      
        if( low < high)
        {          
            while(i < j) 
            {
                while((a[j] >= temp) && (i < j))
                { 
                    j--; 
                }
                a[i] = a[j];
                while((a[i] <= temp) && (i < j))
                {
                    i++; 
                }  
                a[j]= a[i];
            }
            a[i] = temp;
            quiksort(a,low,i-1);
            quiksort(a,j+1,high);
        }
        else
        {
            return;
        }
    }
    int compare(int i,int j)
    {
        if(i>j)
            return i-j;
        else return j-i;
    }
    int main(void)
    {
        int n,k,counta1=0,counta2,countb1=0,countb2,i=0;
        unsigned long long sum=0;
        scanf("%d%d",&n,&k);
        counta2=countb2=n-1;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&b[i]);
        quiksort(a,0,n-1);
        quiksort(b,0,n-1);
        while(i<k)
        {
            int p,q;
            p=compare(a[counta1],b[countb2]);
            q=compare(a[counta2],b[countb1]);
            if(p>q)
            {
                counta1++;
                countb2--;
                sum+=p;
            }
            else
            {
                counta2--;
                countb1++;
                sum+=q;
            }
            i++;
        }
        printf("%llu",sum);
    } 
    
  • 0
    @ 2016-08-02 19:10:20

    明明说两个数组不重的,去重只能得十分,不去重却AC了,白提交三次

    #include<stdio.h>
    void qsort(long a[],long begin_,long end_)
    {
    long key,temp;
    key=a[begin_];
    long i=begin_,j=end_;
    while(i!=j)
    {
    while(j!=i)
    {
    if(a[j]<=key)
    {
    temp=a[j];
    a[j]=a[i];
    a[i]=temp;
    break;
    }
    else j--;
    }
    while(j!=i)
    {
    if(a[i]>key)
    {
    temp=a[j];
    a[j]=a[i];
    a[i]=temp;
    break;
    }

    else i++;

    }
    }
    if(begin_!=i) qsort(a,begin_,i-1);
    if(end_!=i) qsort(a,i+1,end_);

    }
    long A[100000+10],B[100000+10];
    int main()
    {
    long n,k;
    scanf("%ld%ld",&n,&k);
    for(long i=1;i<=n;i++)
    {
    scanf("%ld",&A[i]);
    }
    for(long i=1;i<=n;i++)
    {
    scanf("%ld",&B[i]);
    }
    qsort(A,1,n);
    qsort(B,1,n);
    /*
    for(long i=1;i<=n;i++)
    {
    long pos=i+1;
    while(A[i]==A[pos]&&A[i]!=-1&&pos<=n)
    {
    A[pos]=-1;
    pos++;
    }
    }
    for(long i=1;i<=n;i++)
    {
    long pos=i+1;
    while(B[i]==B[pos]&&B[i]!=-1&&pos<=n)
    {
    B[pos]=-1;
    pos++;
    }
    }
    /
    long temp1,temp2;
    long long sum=0;
    long pa1=1,pa2=n,pb1=1,pb2=n;
    for(long i=1;i<=k;i++)
    {
    /

    while(A[pa1]==-1)
    {
    pa1++;
    }
    while(A[pa2]==-1)
    {
    pa2--;
    }
    while(B[pb1]==-1)
    {
    pb1++;
    }
    while(B[pb2]==-1)
    {
    pb2--;
    }
    */
    temp1=B[pb2]-A[pa1];
    temp2=A[pa2]-B[pb1];
    if(temp1>temp2)
    {
    sum=sum+temp1;
    pb2--;
    pa1++;
    }
    else
    {
    sum=sum+temp2;
    pa2--;
    pb1++;
    }
    }
    printf("%I64d",sum);
    }

  • 0
    @ 2015-03-08 13:28:54

    var
    t1,t2,w1,w2,i,j,k,n,m,s,t:longint;
    a:array[0..100000,0..1]of longint;
    ans:int64;
    procedure qsort(l,r:longint);
    var i,j,x,y:longint;
    begin
    i:=l;j:=r;x:=a[(l+r) div 2,k];
    repeat
    while a[i,k]<x do inc(i);while x<a[j,k] do dec(j);
    if not(i>j) then
    begin
    y:=a[i,k];a[i,k]:=a[j,k];a[j,k]:=y;inc(i);j:=j-1;
    end;
    until i>j;
    if l<j then qsort(l,j);if i<r then qsort(i,r);
    end;
    begin
    readln(n,m);
    for i:=1 to n do read(a[i,0]);readln;
    for i:=1 to n do read(a[i,1]);readln;
    k:=0;qsort(1,n);
    k:=1;qsort(1,n);
    t1:=1;w1:=n;
    t2:=n;w2:=1;
    for i:=1 to m do
    begin
    if abs(a[t1,0]-a[w1,1])>abs(a[t2,0]-a[w2,1]) then
    begin ans:=ans+abs(a[t1,0]-a[w1,1]);inc(t1);dec(w1); end
    else
    begin
    ans:=ans+abs(a[t2,0]-a[w2,1]);dec(t2);inc(w2);
    end;
    end;
    writeln(ans);
    end.

  • 0
    @ 2014-07-13 15:06:46

    测试数据 #0: Accepted, time = 0 ms, mem = 1392 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1388 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1392 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1388 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1388 KiB, score = 10
    测试数据 #5: Accepted, time = 109 ms, mem = 1388 KiB, score = 10
    测试数据 #6: Accepted, time = 93 ms, mem = 1392 KiB, score = 10
    测试数据 #7: Accepted, time = 124 ms, mem = 1388 KiB, score = 10
    测试数据 #8: Accepted, time = 109 ms, mem = 1392 KiB, score = 10
    测试数据 #9: Accepted, time = 109 ms, mem = 1392 KiB, score = 10

  • 0
    @ 2013-12-07 16:39:22

    简单的贪心。
    很容易想到先sort后,然后用头尾指针分别指向a,b两个数组。因为a中最小和b中最大或a中最大和b中最小,肯定是当前最大了,所以只要O(n)的扫一遍,if判断,就能过了。

    详细题解和源程序请见:题解

  • 0
    @ 2013-09-05 20:34:45

    #include <iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #define maxn 100001
    using namespace std;
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    int cmp1(const void *a,const void *b){
    return *(long )a-(long *)b;
    }

    int cmp2(const void *a,const void *b){
    return -cmp1(a,b);
    }
    long n,i,j,k,a[maxn],b[maxn];
    long long ans=0;
    int main(int argc, char *argv[]) {
    cin>>n;
    cin>>k;
    for(i=1;i<=n;i++){
    cin>>a[i];
    }
    for(i=1;i<=n;i++){
    cin>>b[i];
    }
    qsort(a+1,n,sizeof(long),cmp1);
    qsort(b+1,n,sizeof(long),cmp2);
    i=1;
    j=n;
    while(k>0){
    k--;
    if(abs(a[i]-b[i])>abs(a[j]-b[j])){
    ans=ans+abs(a[i]-b[i]);
    i++;
    }
    else{
    ans=ans+abs(a[j]-b[j]);
    j--;

    }
    }
    cout<<ans<<endl;
    }

  • 0
    @ 2013-09-05 20:22:14

    a降序排列
    b升序排列
    令i=1
    j=n
    另k--
    然后用abs(a[i]-b[i])与abs(a[j]-b[j])相比较
    若abs(a[i]-b[i])大 令i++ 和中加上abs(a[i]-b[i]) 然后继续进行,做到k=0为止
    若abs(a[j]-b[j])大 令j-- 和中加上abs(a[j]-b[j]) 然后继续进行,做到k=0为止
    具体代码不贴了

  • 0
    @ 2012-11-04 13:53:34

    ├ 测试数据 01:答案正确... (0ms, 1584KB)

    ├ 测试数据 02:答案正确... (0ms, 1584KB)

    ├ 测试数据 03:答案正确... (0ms, 1584KB)

    ├ 测试数据 04:答案正确... (0ms, 1584KB)

    ├ 测试数据 05:答案正确... (0ms, 1584KB)

    ├ 测试数据 06:答案正确... (0ms, 1584KB)

    ├ 测试数据 07:答案正确... (0ms, 1584KB)

    ├ 测试数据 08:答案正确... (0ms, 1584KB)

    ├ 测试数据 09:答案正确... (0ms, 1584KB)

    ├ 测试数据 10:答案正确... (0ms, 1584KB)

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

    Accepted / 100 / 0ms / 1584KB

    快排竟然没有堆栈溢出?100000的规模啊

    • @ 2016-11-12 18:42:30

      快速排序基于二分,100000的话总共递归20左右,就是用埃尼阿克运行都不会爆栈啊。。

  • 0
    @ 2010-04-08 22:57:02

    切记

    结果要用int64

    我因此WA了一次。

  • 0
    @ 2009-11-10 15:48:27

    RP不错,随机快排

  • 0
    @ 2009-10-12 21:57:36

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

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

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

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

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

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

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

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

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

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

    INT64不能读入!`- - 我读了半天的1234

  • 0
    @ 2009-10-07 13:01:09

    悲剧了。

  • 0
    @ 2009-10-06 15:09:02

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    悲剧啊,如此幼稚的题,考得时候竟然没有加abs~ ~ orz

    type

    atp = array [1..100000] of longint;

    var

    a,b : atp;

    n , k : longint;

    procedure qsort(l,r : longint;var a : atp);

    var i , j , temp , mid : longint;

    begin

    i := l; j := r; mid := a[(l+r) shr 1];

    repeat

    while a[i] < mid do inc(i);

    while a[j] > mid do dec(j);

    if i j;

    if l < j then qsort(l,j,a);

    if i < r then qsort(i,r,a);

    end;

    procedure init;

    var i : longint;

    begin

    readln(n,k);

    for i := 1 to n do read(a[i]); readln; qsort(1,n,a);

    for i := 1 to n do read(b[i]); readln; qsort(1,n,b);

    end;

    procedure main;

    var i,ta,ha,tb,hb : longint; ans : int64;

    begin

    ans := 0; ha := 1; ta := n; hb := 1; tb := n;

    for i := 1 to k do

    begin

    if abs(a[ha] - b[tb]) > abs(a[ta] - b[hb]) then

    begin inc(ans,abs(a[ha] - b[tb])); inc(ha); dec(tb); end else

    begin inc(ans,abs(a[ta] - b[hb])); inc(hb); dec(ta); end;

    end;

    writeln(ans);

    end;

    begin

    init;

    main;

    end.

  • 0
    @ 2009-10-05 15:05:34

    顶talent123

    谢谢!

    qsort秒杀。

  • 0
    @ 2009-10-05 09:50:22

    为什么QSort都这么慢???

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:答案正确... 916ms

    ├ 测试数据 07:答案正确... 900ms

    ├ 测试数据 08:答案正确... 884ms

    ├ 测试数据 09:答案正确... 931ms

    ├ 测试数据 10:答案正确... 931ms

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

    Accepted 有效得分:100 有效耗时:4562ms

    Who can tell me why??

  • 0
    @ 2009-10-04 21:13:11

    program p1662;

    var a,b,c:array[1..1000000] of longint;

    i,j,k,n:longint;

    ans:int64;

    procedure qsort(x,y:longint);

    var g,t,l,r:longint;

    begin

    t:=c[(x+y) div 2];l:=x;r:=y;

    repeat while c[l]>t do inc(l);

    while c[r]

  • 0
    @ 2009-10-04 13:35:29

    比赛时:ans用longint——50分

    然后:ans用int64——AC~

    郁闷·~

信息

ID
1662
难度
4
分类
贪心 点击显示
标签
(无)
递交数
2302
已通过
942
通过率
41%
被复制
2
上传者