问题描述

N个人要按顺序过一座很长的独木桥，每个人的重量和最短过桥时间都不相同。由于独木桥上无法“超车”，后面的人如果追上前面的人，那么后面的人只能减速，和前面的人以同样的速度一起通过，在同一时间到达桥尾。桥的最大承受重量为M_max，当桥上总重量大于M_max时桥会断裂。请问第几个人上桥的时候桥将因承受不住而断裂？

输入

人数N、桥能承受最大质量
接下来有N组数据：第i个人的重量、上桥时刻和正常速度过桥所需时间（注意不是到达桥尾的时间）
每个人的上桥时刻是按1~N的次序排列的
M_max、每个人重量、上桥时刻和下桥时刻都是整数
N≤100，上桥时刻≤50000，每个人过桥时间≤2000

PS：如果有不同人在同一时刻上下桥的情况，可以看作原本在桥上的人先下桥后，另外那个人桥下的人才上桥

输出

如果第m个人上桥的时候桥断裂了，输出m
如果每个人都能安全通过，输出safe
样例输入

9 476
108 0 1202
101 478 1711
104 1515 1078
99 1830 868
81 1941 1951
92 2139 703
114 2575 1462
84 3941 977
87 4045 521

样例输出

6

完整代码：

//#include "pch.h"
#include <iostream>
#include<queue>
using namespace std;
typedef struct PeopleBridge {
	int weight;
	int intime;
	int crosstime;
	int outtime;
} People;						//构建上桥人结构体，包括重量、上桥时间、通过时间、下桥时间
int main()
{
	int N;						//过桥人数
	int M_max;					//桥所能承受的最大重量
	int NowWeight = 0;			//当前时刻桥上的总重量
	cin >> N >> M_max;			//输入
	People p[100];				//N<=100
	queue<People> q;			//独木桥队列
	for (int i = 0; i < N; i++)	//循环输入每个人的重量、上桥时刻和正常速度过桥所需时间
	{
		cin >> p[i].weight >> p[i].intime >> p[i].crosstime;
		p[i].outtime = p[i].intime + p[i].crosstime;
	}
	for (int i = 0; i < N; i++)	//上桥循环
	{
		//当队列不为空并且队首元素的下桥时间在当前的人的上桥时间之前时
		while ((!q.empty())&&q.front().outtime <= p[i].intime)	
		{
			NowWeight -= q.front().weight;	//减去要下桥的人的重量
			q.pop();						//要下桥的人出队列
		}
		q.push(p[i]);						//当前元素入队列
		NowWeight += p[i].weight;			//加上当前元素的重量
		if (NowWeight > M_max)				//判断当前总重量是否超重
		{
			cout << i + 1 << endl;			//若超重，输出第i+1个人上桥的时候桥断裂
			return 0;						//退出程序
		}
		if ((i > 0) && p[i].outtime < p[i - 1].outtime)	//判断当前的人是否能追上前面的人
		{
			p[i].outtime = p[i - 1].outtime;			//若能，在同一时间到达桥尾
		}
	}
	cout << "safe" << endl;					//每个人都能安全通过，输出safe
}

PS:仅供参考，请勿抄袭！！！