7

1 6

1 7

3 2

3 1

2 4

2 5

6 1

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\n",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\n",ans);

}

int main()

{

	input_data();

	sort(a+1,a+1+n,cmp); //对a数组进行排序操作。

	get_ans();

	output_ans();

	return 0;

}