3 Nov 2016 本文阅读量次

【智障模拟赛】 智障的死亡 

【问题描述】
现在有m个位置可以打 sif，有n + 1个人在排队等着打 sif。现在告诉你前n个人每个人需要多长的时间打 sif，问你第n + 1个人什么时候才能打 sif。（前n个人必须按照顺序来）
【输入格式】
第一行两个整数n, m
接下来n行每行一个整数代表每个人所需要用的时间。
【输出格式】
一行一个整数表示答案。
【样例输入】
3 2
1
1
1
【样例输出】
1

思路

第一次的超时方法 ： 使用优先队列(小根堆)存储M个位置， 每次取出优先队列中的top元素， 并且遍历队列使各元素减去top元素， 当队列中元素值 ≤0 时， 令n中剩余元素补位， 直至n=0. 显然地， 遍历队列时浪费大量时间， 导致超时。
考虑更为简便高效的贪心策略 ： 我们将遍历队列的过程转化为向队列中添加新元素， 初始时， 向队列中push m个0， 之后依次枚举每个人(保证n个人按照顺序, 并且保证了贪心策略的正确性)的时候， 取出优先队列 top元素， 计算 top元素值+当前人所需时间 并push到队列， 该值一定为当前人打sif所需的最短时间

技巧

优先队列(priority_queue)默认为大根堆, 我们通过以下三种方法将其转化为小根堆:

  • push元素的时候, 可以push元素的相反数。 比如 序列 5 4 3 2 1， 我们push -5 -4 -3 -2 -1 ，自然的， 优先队列会这样存储: -1 -2 -3 -4 -5, 但要注意取出元素时要取其相反数。
  • 声明优先队列时， 指明其为小根堆:
priority_queue<int, vector<int>, greater<int> > Q;
  • 当优先队列的模板为结构体时, 我们可以在结构体中重载 < 运算符将其转化为小根堆(重载运算符具体见博文：重载运算符):
struct STRUCT {
    int x;
    bool operator< (const STRUCT& A) const {
        return A.x < this->x;
    }
}

代码

超时代码 ：

/*
* Copyright © Eliot
* Date: 2016-11-03
* Author: Eliot
* Description: 超时代码
* QQ: 1161142536
*/

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int N = 0, M = 0;
int nPeople[100001] = { 0 }, p = 0;
priority_queue<int> Q;

priority_queue<int> Transform(int nDecTime) {
	priority_queue<int> Q_Retn;

	while (!Q.empty()) {
		int temp = -Q.top();
		Q.pop();

		temp -= nDecTime;
		if (temp <= 0) {
			N--;
			p++;
			if (nPeople[p] != 0) Q_Retn.push(-nPeople[p]);
		}
		else {
			Q_Retn.push(-temp);
		}
	}

	return Q_Retn;
}

int ans = 0;
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) scanf("%d", &nPeople[i]);
	p = M;
	for (int i = 1; i <= M; i++) Q.push(-nPeople[i]);
	while (N > 0) {
		int nMinTime = -Q.top();

		ans += nMinTime;
		Q = Transform(nMinTime);
		if (Q.size() < M) break;
	}
	
	cout << ans << endl;
	return 0;
}

AC代码 ：

/*
* Copyright © Eliot
* Date: 2016-11-03
* Author: Eliot
* Description: AC代码
* QQ: 1161142536
*/

#include <cstdio>
#include <queue>

using namespace std;

const int MAX = 100010;

int n = 0, m = 0, nMin = 0, k = 0;
int A[MAX] = { 0 };
priority_queue<int, vector<int>, greater<int> > Q;
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
    for(int i = 1; i <= m; i ++) Q.push(0);
    for(int i = 1; i <= n + 1; i ++){
        nMin = Q.top(); Q.pop();
        Q.push(nMin + A[i]);
    }
    printf("%d\n", nMin);
    
    return 0;
}
Tags:
Status:

Share:

Comments: