UVALive 4850 Installations

　　题目大意：有若干个任务，每个任务耗时si，期限为di，同一时间只能做一个任务。对于一个任务，惩罚值为max(0,完成时间-期限)。问怎么安排，使(最大惩罚值+次大惩罚值)最小，O(n^2)。

　　如果没有次大惩罚值，就是一个很显然的贪心了：把任务按di排序，di相同按si排序，一路平推过去。

　　这样可以保证最大值最小，但不能保证(最大+次大)最小。好在这题有十分良心的样例：

　

　　仔细观察一下样例，你会发现：基本上也是按照上面的逻辑做任务，但J2和J6换了一个位置。

　　还有一件非常巧合的事情：J2和J6就是答案。

　　观察一下完全按照上面逻辑做的情况，发现答案是8，最大值是J6(5)，次大值是J2(3)。

　　然后把J2换到J6右边，就变成最大值J2(6)，次大值J6(1)。

　　提示我们可以通过把一个前面的拿出来，扔到原先最大/次大的后一个去。

　　分析一下这样做的结果：后半截不变，拿出来的变成最大值，原来的最大值、次大值减小并作为次大值，最终结果可能会比原答案小。

　　看一下数据，枚举，O(n^2)就可以了。

　　为什么只拿一个就可以了呢？因为拿两个就肯定比不拿要大了(第一次拿出的超过原次大值，第二次的超过原来的最大值)。

　　要不是有样例我一年都想不出这个

#include    <iostream>

#include    <cstdio>

#include    <cstdlib>

#include    <algorithm>

#include    <vector>

#include    <cstring>

#include    <queue>

#include    <complex>

#include    <stack>

#define LL long long int

#define dob double

#define FILE "4850"

using namespace std;

const int N = ;

struct Pair{

  int t,r;

  bool operator <(const Pair &p)const{

    if(r==p.r)return t<p.t;

    return r<p.r;

  }

}A[N];

int n,id,Ans,L[N],R[N];

inline int gi(){

  int x=,res=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')res*=-;ch=getchar();}

  while(ch<=''&&ch>='')x=x*+ch-,ch=getchar();

  return x*res;

}

inline int getmxp(){

  int sum=,mxp=,nmxp=;id=;

  for(int i=R[],p;i<=n;i=R[i]){

    sum+=A[i].t;p=max(,sum-A[i].r);

    if(p>=mxp)nmxp=mxp,mxp=p,id=i;

    else if(p>=nmxp)nmxp=p,id=i;

  }

  return mxp+nmxp;

}

inline void solve(){

  n=gi();R[]=;L[n+]=n;

  for(int i=;i<=n;++i)

    A[i].t=gi(),A[i].r=gi(),L[i]=i-,R[i]=i+;

  sort(A+,A+n+);Ans=getmxp();

  if(!Ans){printf("0\n");return;}

  for(int i=R[],j=id;i!=j;i=R[i]){

    int l=L[i],r=R[i];

    R[l]=r;R[i]=R[j];R[j]=i;

    Ans=min(Ans,getmxp());

    R[j]=R[i];R[l]=i;R[i]=r;

  }

  printf("%d\n",Ans);

}

int main()

{

  freopen(FILE".in","r",stdin);

  freopen(FILE".out","w",stdout);

  int Case=gi();while(Case--)solve();

  fclose(stdin);fclose(stdout);

  return ;

}

Installations