[51nod] #1163 最高的奖励

problem

portal: Highest reward

Description

There are N tasks, each with a latest end time and corresponding reward. Complete this task before the end time and you will receive the reward. The time required to complete each task is 1 unit time. Sometimes it is impossible to complete all tasks, because there may be conflicts in time, which require you to choose. Seeking the highest reward you can get.

Standard Input

Line 1 : A number N, indicating the number of tasks ( 2 $\le$ N $\le$ 50000)
Line 2 to N+1: two number per line, separated by spaces, indicating the latest end time E[i] of task and the corresponding reward W[i]. (1 $\le$ E[i] $\le$ 10⁹)

Standard Output

Output the Highest award available.

Constrain

$2\le N\le 50000$
$1\le E[i]\le 10^9$
$1\le W[i]\le 10^9$

Sample

Input

7
4 20
2 60
4 70
3 40
1 30
4 50
6 10

Output

230

Solution

Analyse

中文版:
 如果你想要得到一个奖励, 那么你就应该在截止时间之前完成这个任务.
 分析已有的样例, 寻找解题的思路
 
 首先, 从前往后: 第1个单位时间, 你有着7种选择, 你可以选择最大的奖励70, 如果你这么做了, 那么你将无法完成截止时间为1且奖励为30的任务, 第2个单位时间, 你还有5种选择, 你可以选择剩余的里面最大的奖励60, 第3个单位时间, 你有4种选择, 此时, 如果你选择奖励为50的, 那么你将失去奖励为40的任务, 如果你选择了奖励为40, 那么下一次你依旧可以选择奖励为50的, 最后第5个单位时间, 你就只能选择完成奖励为10的任务. 由于第3个单位时间选择的时候我们考虑了后面的一些情况, 所以就很难用程序来实现刚才的这个思维过程.
 所以可以试着从后往前:最晚的一个任务的截止时间是6, 所以在第6个单位时间里, 我们只有这一个任务, 所以选择它, 第5个单位时间, 没有任务, 不需要考虑, 第4个单位时间, 我们有三个任务可供选择, 为了保证利益最大化, 我们选择最大的70, 避免我们选择了其他任务而导致该任务过期, 第3个单位时间, 我们有三种选择, 依旧选择最大的50, 第2个单位时间, 选择60, 第1个单位时间, 选择40, 如此便可以很轻松的得到最大奖励. 也可以很轻松的用程序来描述这个过程.

design

 一个数组E, 一个数组W, 用来存储最晚结束时间和对应奖励
 对其由大到小进行排序, 以E数组作为判断条件, W数组跟随E数组做相应的移动即可. 为了保证效率, 修改了快速排序, 使其满足当前设计要求.
 创建一个数组用来存储当前可以完成任务的奖励值, 以样例为例, 当在第6个单位时间的时候, 给该数组插入一个值10, 然后到了计算的时候, 由于只有一个10, 所以将10加上, 然后将10移出数组, 第5个单位时间, 没有可插入的元素, 到了计算的时候, 数组为空, 所以不加任何值, 第4个单位时间, 将20, 70, 50插入数组, 然后从大到小排序, 到了计算的时候, 加上最大的70, 并将70移出数组, 之前的时间依次将奖励添加入数组, 然后在计算时刻输出最大的并踢出数组即可.

code

// program name: highest reward
// Written by: by_sknight
// Date: 2019/3/16

#include <iostream>
using namespace std;

void quickSort(int MainArr[], int FollowArr[], int left, int right);
void swap(int &a, int &b);

class CanDo {
private:
	int *award;	// 在当前条件下, 可以获得的所有奖励
	int num;	// 在当前条件下, 可获得的奖励数量
	int max;	// 当前最多可存放的奖励数量
	void add(int n)
	{
		int i;
		for (i = num - 1; i >= 0 && award[i] < n; i--)
			award[i+1] = award[i];
		if (i == -1)
			award[0] = n;
		else
			award[i+1] = n;
		num++;
	}
public:
	CanDo() {
		award = new int[100];
		num = 0;
		max = 100;
	}
	void insert(int n) {
		if (num < max)
		{	// 意味着还能扔进去奖励
			add(n);
		}
		else
		{	// 意味着已经能满了, 需要扩容
			int *temp = award;
			award = new int[max+100];
			max += 100;
			// 拷贝所有的内容
			for (int i = 0; i < num; i++)
				award[i] = temp[i];
			delete[] temp;	// 释放旧的空间
			add(n);
		}
	}
	int extract()
	{
		int x = award[0];
		for (int i = 0; i < num-1; i++)
			award[i] = award[i+1];
		num--;
		return x;
	}
	int isNull()
	{
		if (num == 0)
			return 1;
		else
			return 0;
	}
};

int main(void)
{
	int N, *E, *W;
	cin >> N;
	E = new int[N];
	W = new int[N];
	for (int n = 0; n < N; n++)
		cin >> E[n] >> W[n];
	// 将这两个数组根据E, 由大到小排序
	quickSort(E, W, 0, N);

	CanDo ca;
	long long total = 0;
	int i = 0;

	for (int time = E[0]; time > 0; time--)
	{
		while (i < N && E[i] == time)
		{
			ca.insert(W[i]);
			i++;
		}
		if (!ca.isNull())
		{
			total = total + ca.extract(); // 加上当前可以取得的最大值
		}
	}

	cout << total << endl;
}

void quickSort(int MainArr[], int FollowArr[], int left, int right)
{
	// 递归终点条件
	if (right - left <= 1)
		return;
	// 从主数组中选择一个基准
	int pivot = MainArr[right-1];
	int storeIndex = left;
	for (int i = left; i < right - 1; i++)
	{
		if (MainArr[i] > pivot)
		{
			swap(MainArr[i], MainArr[storeIndex]);
			swap(FollowArr[i], FollowArr[storeIndex]);
			storeIndex++;
		}
	}
	swap(MainArr[right-1], MainArr[storeIndex]);
	swap(FollowArr[right-1], FollowArr[storeIndex]);

	quickSort(MainArr, FollowArr, left, storeIndex);	// 排左边
	quickSort(MainArr, FollowArr, storeIndex+1, right);	// 排右边
}

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

最后

以上就是缓慢楼房为你收集整理的[51nod] #1163 最高的奖励的全部内容，希望文章能够帮你解决[51nod] #1163 最高的奖励所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。