|
Ctrl AC！一起 AC！
原题：忘题戳这
资料：C++ 操作符重载????????C++ 优先列队???????
? ? ? ? ??优先列队中的操作符重载
? ? ? ? ??friend bool
分析：贪心，哪头牛先产奶就立即给它安排畜栏。
? ? ? ? ? ?如果之前的畜栏都没用完，就先给个新的。
? ? ? ? ? ?如果之前的畜栏有空出来的，就给它这个畜栏。
上述用优先队列实现，用队列存畜栏，正在使用中的畜栏最先用完的放在队列最前头（即第一考虑对象，空了就用它，没有就新建）
AC代码：
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct cowform {//牛的信息结构体
int s, e, ID;//分别表示开始，结束，牛的id，（区别不同牛）
friend bool operator < (const cowform& a, const cowform& b) {//操作符重载，实现队列排序规则
return a.e > b.e;
}
};
bool cmp(cowform a, cowform b) {
if (a.s == b.s) return a.e < b.e;
else return a.s < b.s;
}//牛的处理顺序的排序规则
int n;
cowform cow[50005];
int usenum[50005];//记录每头牛放进的畜栏
priority_queue<cowform> q;//优先队列，满足操作符重载的排序规则
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> cow[i].s >> cow[i].e;
cow[i].ID = i;
}
sort(cow, cow + n, cmp);
int num = 1;
cowform firstcow = cow[0];
usenum[cow[0].ID] = num;
q.push(firstcow);//准备工作
for (int i = 1; i < n; i++) {
cowform nowcow = q.top();
if (nowcow.e < cow[i].s) {//如果能，就用队列头的畜栏号
usenum[cow[i].ID] = usenum[nowcow.ID];
q.pop();
q.push(cow[i]);
}
else {//不能则加畜栏
usenum[cow[i].ID] = ++num;
q.push(cow[i]);
}
}
cout << num << endl;
for (int i = 0; i < n; i++) {
cout << usenum[i] << endl;//不要把i写出cow[i].ID,因为sort 排序已打乱
}
return 0;
}
感谢阅读！！！
Ctrl AC！一起 AC！?
|