單組測試數(shù)據(jù)。

第一行包含兩個(gè)整數(shù)n 和H (1 ≤ n ≤ 1000，1 ≤ H ≤ 1000000000)，表示可供選擇的城市數(shù)目和時(shí)間限制。

接下來n行，每行有兩個(gè)整數(shù)hi, pi (1 ≤ hi ≤ H, 1 ≤ pi ≤ 1000)，第i個(gè)城市的兩個(gè)屬性，即直徑和能容納人口數(shù)。

輸出最多能居住的人口數(shù)目。

5 10

1 1

1 1

2 2

3 3

4 4

11

我到現(xiàn)在還在想為什么這道題僅僅是20分的一道題，一開始做的時(shí)候題意都沒能完全理解。。。理解了之后發(fā)現(xiàn)情況怎么這么多，要考慮的因素怎么這么多，用優(yōu)先隊(duì)列是肯定的，怎么用都是個(gè)問題。。。最后是一位大神把代碼發(fā)過來，跑了幾次之后，才理解。但現(xiàn)在，對(duì)這道題真的是快要膜拜了，無論是出題人還是寫出這種做法的人，可能是我水平現(xiàn)在太弱了，這個(gè)代碼仔細(xì)想了想，寫得是真的6。膜拜~

將距離按照降序排列，然后在只有滿足當(dāng)前數(shù)量<i的時(shí)候往里面添加元素，彈出來的是當(dāng)前隊(duì)列中的人口最少的城市，隊(duì)列中的是被選中的滿足接下來長度要求的城市，然后在這一輪中添加這個(gè)距離的所有城市，之后如果城市數(shù)量超出，再將人口最少的城市排除。也就是說，隊(duì)列里面是符合長度要求的人口最多且在當(dāng)前狀況下數(shù)量最多的城市。

膜拜大神~

代碼：

#include <iostream>

#include <vector>

#include <queue>

#pragma warning(disable:4996)

using namespace std;

const int N = 1005;

int n,H;

vector <int> v[N];

int main()

{

	scanf("%d%d",&n,&H);

	for(int h,p,i=0;i<n;i++)

	{

		scanf("%d%d",&h,&p);

		int x = min(n,H-h);

		v[x].push_back(p);

	}

	priority_queue<int>q;

	int ans = 0;

	for(int i=1,s=0;i<=n;i++)

	{

		for(;q.size()>=i;q.pop())

			s+=q.top();

		for(auto &p:v[i])

		{

			q.push(-p);

			s += p;

		}

		for(;q.size()>i+1;q.pop())

		{

			s += q.top();

		}

		ans = max(ans,s);

	}

	printf("%d\n",ans);

}

總結(jié)

以上是生活随笔為你收集整理的51nod 1475：建设国家 优先队列的好题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。