解题思路
题面中提到后面的人可以找前面的是朋友的人夹塞,让朋友帮忙办理业务,朋友的办理时间会累加。这个过程可以看作一个插队的过程,即把自己插到朋友的后面。由于朋友帮自己办业务是紧接着他自己刚办完的业务连续办理的,所以自己插在朋友后面和让朋友累加办理时间是等价的。
因此我们可以使用队列模拟,每次 pop 出队首,表示此人已办理完毕。接下来找一个人放到队列中作为下一个要办理的人。而下一个的人选是有要求的,即优先寻找一个到达时间不晚于自己离开时间的朋友,让他排在自己后面(插队),如果找不到则按原顺序找自己后面的第一个人,让他排在自己后面。这样不断循环并累加等待时间,直到队列为空即可。
参考代码
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;
struct info {
char name[4];
int t;
int p;
} a[10000];
int Hash(char *s) { // 把字符串哈希成数字,防止超时
return (s[0]-'A')*26*26 + (s[1]-'0')*26 + s[0]-'0';
}
int main(int argc, char const *argv[]) {
int n, m, l;
char s[4];
bool vis[10000] = {false}; // 标记是否已办理完毕
scanf("%d %d", &n, &m);
set<int> st[100]; // 朋友圈集合
map<int, int> mp; // 映射人名到朋友圈编号
for(int i=0; i<m; ++i) {
scanf("%d", &l);
while(l--) {
scanf("%s", s);
st[i].insert(Hash(s));
mp[Hash(s)] = i;
}
}
for(int i=0; i<n; ++i) {
scanf("%s %d %d", a[i].name, &a[i].t, &a[i].p);
if(a[i].p > 60) a[i].p = 60;
}
queue<info> q;
q.push(a[0]);
vis[0] = true;
int last = a[0].t+a[0].p;
int sum = 0;
while(!q.empty()) {
info f = q.front();
q.pop();
printf("%s\n", f.name);
bool found = false;
for(int i=1; i<n; ++i) { // 寻找一个到达时间不晚于自己办理结束时间的朋友
if(vis[i]) continue;
if(a[i].t > last) break;
if(st[mp[Hash(f.name)]].count(Hash(a[i].name))) {
q.push(a[i]);
vis[i] = true;
found = true;
sum += last-a[i].t;
last += a[i].p;
break;
}
}
if(!found) { // 未找到,则按原顺序找下一个人
for(int i=1; i<n; ++i) {
if(vis[i]) continue;
q.push(a[i]);
vis[i] = true;
sum += max(0, last-a[i].t); // 等待时间可能为 0(窗口空闲一段时间)
if(a[i].t > last) last = a[i].t;
last += a[i].p;
break;
}
}
}
printf("%.1f\n", 1.0*sum/n);
return 0;
}
还不快抢沙发