poj 2010 Moo University - Financial Aid 优先队列

缘起

日常浪费生命 poj 2010 Moo University - Financial Aid

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
奶牛大学：奶大招生，从C头奶牛中招收N头(奇数)。它们分别得分score_i，需要资助学费aid_i。希望新生所需资助不超
过F，同时得分中位数最高。求此中位数。

ps: 中位数是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据. 详见【1】

【输入】
第一行 N,C,F, 后面是C行，每行两个整数(score_i, aid_i)
1 <= N <= 19,999
N <= C <= 100,000
0 <= F <= 2,000,000,000
1<=score_i<=2,000,000,000
0 <= aid_i <=100,000

【输出】
最大的中位数. 如果F不足以支持N位小牛入学，输出-1

【样例输入】
3 5 70
30 25
50 21
20 20
5 18
35 30

【样例输出】
35

【限制】
1s

【hint】
Sample output:If Bessie accepts the calves with CSAT scores of 5, 35, and 50, the 
median is 35. The total financial aid required is 18 + 30 + 21 = 69 <= 70.

本题的想法是这样的——二分答案. 即二分中位数. 首先将牛数组按照score升序排序，假定 a[i]作为中位数. 则可以获取到<=它的数字集合和>=它的数字集合. 然后前面的数字是否能取出(N-1)/2 头牛的aid值之和+后面能否取出(N-1)/2 头牛的aid值之和+a[i]这头牛的aid值能否<=F, 如果可以的话，a[i]是可以作为中位数的.

从贪心的角度，我们自然希望从需要资助较少的牛中选取。 所以我们将所有的牛先入关于资助属性的小根堆. 然后里面的元素还要记录它在排序后的数组中的索引. 则不断的出堆. 出堆的元素的索引<i的话,就是属于前面的，直至属于前面的元素个数=(N-1)/2. 如果出堆的元素的索引>i的话,就是属于后面的,直至属于后面的元素个数=(N-1)/2

只要堆不空，就不断进行.

按照此思想，写出如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,c,f,loop;
struct Cow
{
	int score, aid, i;
	bool operator <(const Cow &o) const
	{
		return score<o.score;
	}
}cows[100005];

struct cpm
{
	bool operator()(Cow &a, Cow &b)
	{
		return a.aid>b.aid; // 需要资助越少, 优先级越高
	}
};

priority_queue<Cow, vector<Cow>, cpm> pq[2]; // 两个优先队列倒来倒去

bool ok(int x) // 看看cows[x].score作为中位数可不可以
{
	int _less = 0, _more = 0,sum = cows[x].aid; // _less是索引<x的, _more是索引>x的, sum 是当前总资助之和
	bool ret = true;
	while(!pq[loop].empty()) // 使用优先队列 pq[loop]
	{
		if (sum>f && (_less<n || _more<n)) // 如果在达成目标之前就超出了总预算f的话,则false
		{
			ret = false;
		}
		Cow top = pq[loop].top();
		pq[loop].pop();
		pq[1-loop].push(top); // 扔进另一个堆
		if (!ret) // 如果已经失败, 就只是将数据从一个堆扔进另一个堆中而已
		{
			continue;
		}
		if (top.i<x && _less<n)
		{
			_less++;
			sum += cows[top.i].aid;
		}
		else if (top.i > x && _more<n)
		{
			_more++;
			sum+=cows[top.i].aid;
		}
	}
	return ret&&sum<=f&&_less==n && _more==n;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d%d", &n, &c, &f);
	n=(n-1)>>1;
	for (int i = 0; i<c; i++)
	{
		scanf("%d%d", &cows[i].score, &cows[i].aid);
	}
	sort(cows, cows+c); // 按照score升序排序
	if (!n) // 如果原本n=1,则需要特别处理
	{
		for (int i = c-1; ~i; i--)
		{
			if (cows[i].aid<=f)
			{
				printf("%d\n", cows[i].score);
				return 0;
			}
		}
	}
	for (int i = 0;i<c;i++)
	{
		cows[i].i = i;
		pq[0].push(cows[i]);
	}
	int lo = 0, hi = c-1, ans=-1,mid;
	while(lo<=hi) // 二分答案(因为要求满足条件的最大值)
	{
		mid = (lo+hi)>>1;
		if (ok(mid))
		{
			lo = mid+1;
			ans = mid;
		}
		else
		{
			hi = mid-1;
		}
		loop = 1-loop;
	}
	printf("%d\n", ~ans?cows[ans].score:-1);
	return 0;
}

很不幸，被T掉了(根据自己偷偷下载的usaco历年数据，上述算法都能得到正确的结果，所以就是单纯的慢)

Status Time Limit Exceeded
Length 1782
Lang C++
Submitted 2019-08-29 19:56:11
Shared
RemoteRunId 20816586

那么改进点在哪里呢? 或者说上面的算法浪费时间的点在哪里呢? 感觉就是2个队列倒来倒去太费时间啦~ 所以优化的方法是还不如对奶牛数组根据aid字段再排一次序（即下面的t）.

然后又写下了如下的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,c,f;
struct Cow
{
	int score, aid, i;
	bool operator <(const Cow &o) const
	{
		return score<o.score;
	}
}cows[100005], t[100005]; // cows是依据score升序排序, t是依据aid升序排序

bool cmp(const Cow &a, const Cow &b)
{
	return a.aid<b.aid;
}

bool ok(int x) // 看看cows[x].score作为中位数可不可以
{
	int _less = 0, _more = 0,sum = cows[x].aid; // _less是索引<x的, _more是索引>x的, sum 是当前总资助之和
	for(int i = 0; i<c; i++)
	{
		if (sum>f && (_less<n || _more<n)) // 如果在达成目标之前就超出了总预算f的话,则false
		{
			return false;
		}
		if (_less==n && _more==n && sum<=f) // 如果满足了
		{
			return true;
		}
		if (t[i].i<x && _less<n)
		{
			_less++;
			sum += t[i].aid;
		}
		else if (t[i].i > x && _more<n)
		{
			_more++;
			sum += t[i].aid;
		}
	}
	return sum<=f&&_less==n && _more==n;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d%d", &n, &c, &f);
	n=(n-1)>>1;
	for (int i = 0; i<c; i++)
	{
		scanf("%d%d", &cows[i].score, &cows[i].aid);
	}
	sort(cows, cows+c); // cows按照score升序排序
	if (!n) // 如果原本n=1,则需要特别处理
	{
		for (int i = c-1; ~i; i--)
		{
			if (cows[i].aid<=f)
			{
				printf("%d\n", cows[i].score);
				return 0;
			}
		}
	}
	for (int i = 0;i<c;i++)
	{
		t[i].i  = cows[i].i = i;
		t[i] = cows[i];
	}
	sort(t,t+c,cmp); // t是按照aid升序排序的
	int ans = c-1;
	while(~ans&&!ok(ans)) // 最坏O(N*C)
	{
		ans--;
	}
	printf("%d\n", ~ans?cows[ans].score:-1);
	return 0;
}

结果还是被T掉了。 很显然的啦——第82行太浪费时间啦~ 而且注意，本题进行二分答案是错误的，因为二分答案的前提是答案具备单调性.

结果没办法——找了题解. 其实我们只需要首先按照score升序排序. 然后O(n)枚举中位数所在的索引. 然后左边需要得到[0,….,i-1]中(n-1)>>1个aid的最小和. 右边只需要得到[i+1,…,n) 中(n-1)>>1个元素的aid的最小和. 而这两个东西可以预处理的. 即我们要预处理的对象是

dp[i] 为 [0,…,i) 即前i头牛中取(n-1)>>1 的aid最小和.

dpp[i]为[c-i,c) ，即尾部i头牛中取(n-1)>>1的aid最小和.

以dp[i]为例, 如果i<(n-1)>>1的话，则不可能, 最小和就是inf. 如果i>=(n-1)>>1的话，其实就类似于求第k小的问题. 维护一个(n-1)>>1的大根堆. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef long long LL; // 注意, 

LL n,c,f;
LL dp[100005],dpp[100005],inf = 1LL<<60;
priority_queue<LL, vector<LL>, less<LL> >pq[2]; // 大根堆 pq[0]维护dp, pq[1]维护dpp, dp[i]是[0,..,i-1]选出n个牛的aid的最小和,dpp[i]是(i,...,c-1]选择n个牛的aid的最小和
struct Cow
{
	LL score, aid;
	bool operator <(const Cow &o) const
	{
		return score<o.score;
	}
}cows[100005]; // cows是依据score升序排序, t是依据aid升序排序

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld%lld%lld", &n, &c, &f);
	n=(n-1)>>1;
	for (int i = 0; i<c; i++)
	{
		scanf("%lld%lld", &cows[i].score, &cows[i].aid);
	}
	sort(cows, cows+c); // cows按照score升序排序
	if (!n) // 如果原本n=1,则需要特别处理
	{
		for (int i = c-1; ~i; i--)
		{
			if (cows[i].aid<=f)
			{
				printf("%lld\n", cows[i].score);
				return 0;
			}
		}
	}
	for (int i = 0; i<n; i++)
	{
		pq[0].push(cows[i].aid);
		dp[n]+=cows[i].aid;
		dp[i] = inf;
	}
	for (int i = c-1; i>c-n-1; i--)
	{
		pq[1].push(cows[i].aid);
		dpp[c-n-1]+=cows[i].aid;
		dpp[i] = inf;
	}
	for (int i = n;i<c; i++)
	{
		int top = pq[0].top();
		if (cows[i].aid>=top) // 比堆最大的还大, 肯定不会是n个最小的数,所以continue掉
		{
			dp[i+1] = dp[i];
			continue;
		}
		else
		{
			pq[0].pop();
			pq[0].push(cows[i].aid);
			dp[i+1] = dp[i]-top+cows[i].aid;
		}
	}
	for (int i = c-n-1;~i; i--)
	{
		int top = pq[1].top();
		if (cows[i].aid>=top) // 比堆最大的还大, 肯定不会是n个最小的数,所以continue掉
		{
			dpp[i-1] = dpp[i];
			continue;
		}
		else
		{
			pq[1].pop();
			pq[1].push(cows[i].aid);
			dpp[i-1] = dpp[i]-top+cows[i].aid;
		}
	} // 预处理完毕, 预处理的复杂度是
	LL ans = c-1;
	for (; ~ans; ans--)
	{
		if (cows[ans].aid+dp[ans]+dpp[ans]<=f)
		{
			break;
		}
	}
	printf("%lld\n", ~ans?cows[ans].score:-1);
	return 0;
}

ac情况

Status Accepted
Time 188ms
Memory 3352kB
Length 1799
Lang C++
Submitted 2019-08-30 09:04:35
Shared
RemoteRunId 20817903

参考

【1】https://zhidao.baidu.com/question/303958718630754284.html