Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为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，注意可能还有其他方法。
你的任务就是找到一个完成作业的顺序获得最大学分。
【输入格式】
第一行一个整数N，表示作业的数量。接下来N行，每行包括两个整数，第一个整数表示作业的完成期限，第二个数表示该作业的学分。【输出格式】
输出一个整数表示可以获得的最大学分。保证答案不超过longint范围。
【数据规模】
对于所有数据，N<=1000000，作业的完成期限均小于700000。 对于部分数据，N<=1000； 对于部分数据，N<=10000； 对于部分数据，N<=100000； 对于部分数据，作业的完成期限小于100； 对于部分数据，作业的完成期限小于1000；
Sample Input1
7 1 6 1 7 3 2 3 1 2 4 2 5 6 1
Sample Output1
15
【题解1】
按照期限。从大到小排序。设置一个变量maxtime,表示当前在安排哪一天的作业。一开始maxtime为所有的作业最大期限。如果遇到有a[i].deadline==maxtime,则把这些a[i]加入到大根堆中。然后为maxtime分配一个作业。然后maxtime递减，再为递减后的maxtime分配一个作业。这样做的意义在于。排除掉了当前的日期超过了最后期限的问题。我们处理的作业都是可以在当前枚举的日子做的作业。而我们给其选一个最优值->最大值。
难点就只在堆操作上了。
一开始的排序可以改为链式存储。最大为70万。
【代码1】
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct data
{
int deadline,points;
};
data a[1000009];
int dui[1000009],size = 0,pos,ans = 0;
void input_data()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++) //输入n个作业的信息。
scanf("%d%d",&a[i].deadline,&a[i].points);
}
int cmp(const data &a,const data &b) //这是sort函数的比较函数 按照最后时限从小到大排序
{ //最后我们会从大到小处理。
if (a.deadline < b.deadline)
return 1;
return 0;
}
void up_adjust(int p) //把在p位置上的数试着往上调整
{
int x = dui[p]; //先将其取出来
int i = p,j = p/2;
while (j > 0)
{
if (dui[j] < x) //要调整的时候不改变x直接将a[j]赋值给a[i]。
{
dui[i] = dui[j];
i = j; //然后再往上调整
j = i/2;
}
else //不需要调整了 则结束。
break;
}
dui[i] = x;
pos = i;//可能还要往下调整，所以记录其放在了哪里。
}
void down_adjust(int p) //把在堆中p位置上的数字往下调整。
{
int x = dui[p];
int i = p,j = p*2; //获取其儿子节点
while (j <= size)
{
if (j<size && dui[j+1] > dui[j]) //获取它们中的较大值。如果是小根堆则相反。
j++;
if (x < dui[j]) //调整。
{
dui[i] = dui[j];
i = j;
j = i*2;
}
else
break;
}
dui[i] = x; //把x赋值到恰当的位置
}
void get_ans()
{
int maxtime = a[n].deadline; //从最大时限开始
int tt = n;
while (tt >= 1 || maxtime > 0) //往前枚举
{
while ( tt > 0 && maxtime == a[tt].deadline) //如果和当前枚举到的时限一样
{
size++; //则把它们加入到堆中
dui[size] = a[tt].points;
up_adjust(size);
down_adjust(pos);
tt--;//同时减少a数组的末指针
}
if (size > 0) //如果堆中还有元素。就把它放在今天完成
{
ans+= dui[1];
dui[1] = dui[size];
size--;
down_adjust(1);
}
maxtime--;
if (maxtime == 0) //如果已经枚举完天数则结束。
break;
}
}
void output_ans()
{
printf("%d
",ans);
}
int main()
{
input_data();
sort(a+1,a+1+n,cmp);
get_ans();
output_ans();
return 0;
}
【题解2】与思路一有点不同。我们把作业按照分数从大到小排序。然后按分数从大到小的顺序给它们分配一个合适的位置。即在deadline和它之前的位置找一个最近的。这样得到的效果和题解1类似。可以想一下。所有的作业，必然都会在某一个maxtime被全部加入。那
一瞬间，我们要获得其最大值。然后放在maxtime的位置。而我们这样做。正是保证了最大值都能找到一个合适的位置。找到这样一个位置，需要用到并查集。
【代码2】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[700001],n,max_deadline = 0,ans =0 ; //最大期限，用来初始化并查集。
struct zuoye //这个结构体。用来记录每个作业的信息。
{
int deadline,points;
};
zuoye a[1000001];
void input_data()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++) //输入n本作业的信息。
{
scanf("%d%d",&a[i].deadline,&a[i].points);
if (a[i].deadline>max_deadline) //更新最大期限值。
max_deadline = a[i].deadline;
}
}
int cmp(const zuoye &a,const zuoye &b) //sort函数的比较函数。
{ //分数从大到小排
if (a.points > b.points)
return 1;
return 0;
}
int findfather(int x) //这是并查集的找根节点函数
{
if (f[x] !=x)
f[x] = findfather(f[x]); //路径压缩。
return f[x];
}
void get_ans()
{
for (int i = 0;i<= max_deadline;i++) //初始化并查集
f[i] = i;
for (int i = 1;i <= n;i++)
{
int x = findfather(a[i].deadline);//找一下如果最后期限是a[i].deadline。其能够放在哪里
if (x>0) //如果大于0则表示有这样一天，可以用来做这份作业
{
ans+=a[i].points; //直接累加上答案 即可。
f[x] = f[x-1]; //这里不能写成f[a[i].deadline] = f[x-1]。
//因为a[i].deadline 并不是a[i].deadline的根节点。
//不会把其根节点x的所有儿子节点接到f[x-1]上。
}
}
}
void output_ans()
{
printf("%d
",ans);
}
int main()
{
input_data();
sort(a+1,a+1+n,cmp); //对a数组进行排序操作。
get_ans();
output_ans();
return 0;
}