P1190 接水问题

题目地址

---

注意点：

• 每一个模块完成后都应进行测试.
• 编程前应当首先自行模拟每个样例.

---

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=2e4,MAXM=1e3;
int restTime[MAXM];//每个水龙头的剩余使用时间 
int m;//龙头数量 
struct Spigot{
	int restTime;
	bool operator <(Spigot another)const{
		return restTime>another.restTime;
	}
};
int remoteTime(){
	priority_queue<Spigot> q;
	for(int i=1;i<=m;i++){
		if(restTime[i])q.push(Spigot{restTime[i]});
	}
	if(q.empty())return 0;//特殊情况 
	int remoteVal=q.top().restTime;
	for(int i=1;i<=m;i++){
		if(restTime[i]){
			if(restTime[i]>=remoteVal)restTime[i]-=remoteVal;
			else restTime[i]=0;
		}
	}
	return remoteVal;
}
int getEmptyIndex(){//返回空闲位置 
	for(int i=1;i<=m;i++){
		if(!restTime[i])return i;
	}
	return 0;
}
bool hasPerson(){//是否还有人接水 
	for(int i=1;i<=m;i++){
		if(restTime[i])return 1;
	}
	return 0;
}
int w[MAXN];//每个人的接水量
int main(){
	int n;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=m;i++){
		restTime[i]=w[i];//第一批人 
	}
	int timeCnt=remoteTime();//先结束掉一个任务 
	int nowPersonIndex=m+1;//当前队首的人 
	while(getEmptyIndex()){
		while(getEmptyIndex()&&nowPersonIndex<=n){//如果还有空位置 
			restTime[getEmptyIndex()]=w[nowPersonIndex];
			nowPersonIndex++;
		}
		timeCnt+=remoteTime();
		if(nowPersonIndex>n){
			while(hasPerson()){
				timeCnt+=remoteTime();
			}
			break;
		}
	}
	printf("%d
",timeCnt);
	return 0;
}