奶牛们的杂技

本是古典何须时尚 2022-04-03 05:56 171阅读 0赞

###  ###

题目描述

在我农场上有N头牛（1<=N<=50000），我想出了一个杂技特技：站到彼此上面，形成一个有一定高度的垂直堆叠，我就让这些牛来练习这个杂技,牛正在试图弄清楚它们应该在这堆奶牛中排列的顺序。每头N头牛具有相关的体重(1<=W\_i<=10000)和强度(1<=S\_i<=1000000000)。一头牛倒下的风险等于它身上所有牛的总体重（当然不包括它自己的体重）减去它的强度（这样一来，一头更强壮的牛的风险就更低）。你的任务是确定牛的顺序，使任何一头牛的最大风险最小化。

输入

第1行：整数N为单行。

行2…N+1：行i+1用两个空分整数W和S描述牛。

输出

一个单一的整数，给出所有奶牛的最大风险，在任何优化排序，使风险最小化。

#### 分析： ####

这道题是很有趣的贪心题……

一开始可能我们会无从下手……因为直接看是看不出来啥的，只按照重量或者承受能力也是不行的。

我们考虑一个新套路，选择两头奶牛，把他们进行交换，看怎么样贡献会比较大。

我们假设前面的奶牛总重为w，第一头奶牛重为w1，承受能力为s1，第二头同理为w2，s2，那么，第一头的压扁程度是w-s1,第二头的是w+w1-s2，而交换之后，第一头的是w-s2,第二头的是w+w2-s1.

我们发现，w+w2-s1必然比w-s1大，而w+w1-s2必然比w-s2大，所以我们只要比较w+w2-s1和w+w1-s2即可，移项之后发现，w+s更大的那只奶牛放在下面更优，所以我们按这个指标排序计算即可。\`

#include"stdio.h"
    #include"string.h"
    typedef struct {
      long long weight;
      long long strong;
      long long S;
    }CROW;
    CROW crows[50000];
    //数据较多，需要手动快排
    void swap(CROW x[],long long start,long long end)
    {
        CROW t;
        t=x[start];
        x[start]=x[end];
        x[end]=t;
    }
    long long location(CROW crows[],long long start,long long end)
    {
        CROW Key;
        CROW T;
        Key=crows[start];
        while(start<end)
        {
            while(start<end&&crows[end].S>=Key.S)
                end--;
          
            swap(crows,start,end);
            while(start<end&&crows[start].S<=Key.S)
                start++;
          
            swap(crows,start,end);
        }
        return start;
    }
    void qsort(CROW crows[50000],long long low,long long high)
    {
        long long locale;
        if(low<high)
        {
            locale=location(crows,low,high);
            qsort(crows,low,locale-1);
            qsort(crows,locale+1,high);
        }
    }
    int main()
    {
        long long N;
        long long i,j,k,risk,sum;
        while(~scanf("%lld",&N))
        {   risk=0;sum=0;
            for(i=0;i<N;i++)
                {scanf("%lld%lld",&crows[i].weight,&crows[i].strong);
                 crows[i].S=crows[i].weight+crows[i].strong;
                }
            qsort(crows,0,N-1);
            sum=0;
            //  printf("\n");
            //for(i=0;i<N;i++)
             //   printf("%lld %lld \n",crows[i].weight,crows[i].strong);
            risk=sum-crows[0].strong;
            sum=crows[0].weight;
            for(i=1;i<N;i++)
            {
              if(risk<sum-crows[i].strong)
                risk=sum-crows[i].strong;
    
                sum+=crows[i].weight;
    
            }
        printf("%lld\n",risk);
    
        }
    }