一本通网站 1430:家庭作业

原题  传送门

【题目描述】

老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10,要求在6天内交,那么要想拿到这10学分,就必须在第6天结束前交。

每个作业的完成时间都是只有一天。例如,假设有7次作业的学分和完成时间如下:

作业号 1 2 3 4 5 6 7
期限 1 1 3 3 2 2 6
学分 6 7 2 1 4 5 1

最多可以获得15学分,其中一个完成作业的次序为2,6,3,1,7,5,4,注意可能d还有其他方法。

你的任务就是找到一个完成作业的顺序获得最大学分。

【输入】

第一行一个整数N,表示作业的数量。

接下来N行,每行包括两个整数,第一个整数表示作业的完成期限,第二个数表示该作业的学分。

【输出】

输出一个整数表示可以获得的最大学分。保证答案不超过longint范围。

【输入样例】

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

【输出样例】

15

第一眼看这个题,和智力大冲浪有点像,甚至还比那个题简单些,不用判断做不完怎么办。

贪心策略:

为了使学分尽可能的多,我们要尽可能得做学分多的作业,我们先按照学分从大到小排序,然后枚举每一个作业,尽量让这个作业贴着期限完成;

我们可以从某一个作业的期限往前找,若找到没安排作业的时间点就将它安排上。

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct homework
{
    int k,date;
}a[1000001];
int read()
{
    char ch=getchar();
    int a=0,x=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') x=-x;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        a=(a<<3)+(a<<1)+(ch-'0');
        ch=getchar();
    }
    return a*x;
}
int cmp(homework x,homework y)
{
    return x.k>y.k;              //按照学分从大到小排序 
}
int n,sum,hash[1000001];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].date=read();
        a[i].k=read();
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        int bj=1;
        for(int j=a[i].date;j>=1;j--) //尽量让作业贴着期限做,来减少对其他作业的影响 
        {
            if(hash[j]==0)
            {
                hash[j]=1;
                bj=0;
                sum+=a[i].k;
                break;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

但是将这份代码交上去后我们发现有两个点TLE了!我们要进一步优化!

如果我们对某一个作业 i 进行安排,发现从a[i].date枚举到1它们的hash都为1,也就是说:从1~a[i].date都已经安排满了,安排不了其他的作业了;

我们可以用q来记录这个a[i].date,对于后面的作业,如果它的期限a[i+1].date<=q,说明这个作业一定安排不了,我们直接跳出就好了,不用再枚举了;

AC代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct homework
{
    int k,date;
}a[1000001];
int read()
{
    char ch=getchar();
    int a=0,x=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') x=-x;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        a=(a<<3)+(a<<1)+(ch-'0');
        ch=getchar();
    }
    return a*x;
}
int cmp(homework x,homework y)     //按照学分从大到小排序 
{
    return x.k>y.k;
}
int n,sum,q,hash[1000001];
int pan(int x)
{
    for(int i=a[x].date;i>=1;i--)
    {
        if(hash[i]==0) 
        {
            hash[i]=1;
            return 1;
        }
    }
    q=a[x].date;                   //如果到了这里,说明1~a[x].date已经安排满了,用q记录下来 
    return 0;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].date=read();
        a[i].k=read();
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].date<q) continue; //直接跳出,节省时间 
           if(pan(i)) sum+=a[i].k;    
    }
    printf("%d
",sum);
    return 0;
}

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注