UVa11729

题目链接

简介:
n个任务分配给n个部队做,每个部队都需要交代B的时间,执行J的时间

分析:
直觉告诉我们,执行时间长的任务需要早交代
那我们直接按照执行时间排序,一个一个交代就好了

为什么我们这么做事对的呢
TA:贪心不要证明
假设我们交换两个相邻的任务X和Y(交换前X在Y之前,交换后X
在Y之后),
不难发现,其他任务的完成时间没有影响,那么我们看着两个任务

情况一

交换之前,任务Y比X先结束
不难发现这样之后答案不会更好
这里写图片描述

情况二

交换之前,X比Y先结束
因此交换之后不会变优的重要条件是:
交换后X的结束时间不比交换前Y的结束时间早
这个条件可以写成:B[Y]+B[X]+J[X]>=B[x]+B[Y]+J[Y]
化简得J[X]>=J[Y],所以说我们要把执行时间长的先进行
这里写图片描述

//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;
struct node{
    int B,J;
};
node a[N];
int n;

int cmp(const node &a,const node &b)
{
    return a.J>b.J;               //J  执行时间 
}

int main()
{
    int cnt=0;
    while (scanf("%d",&n)!=EOF&&n)
    {
        for (int i=1;i<=n;i++)
            scanf("%d%d",&a[i].B,&a[i].J);

        sort(a+1,a+1+n,cmp);
        int ans=0,time=0;
        for (int i=1;i<=n;i++)
        {
            time+=a[i].B;
            ans=max(ans,time+a[i].J);
        }

        printf("Case %d: %d
",++cnt,ans);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/wutongtong3117/p/7673024.html