cf1267 A Apprentice Learning Trajectory 贪心:使用multiset维护当前最小值

//202009031431 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <vector> #define ll long long #define START false #define END true #define pb push_back using namespace std; const int N = 2e5+100; struct Node{ ll st, len;//时刻，时长 bool dir;//false表示开始，true表示结束 Node(ll l, bool flag, ll ti){ st = l, dir = flag, len = ti; } bool operator<(const Node& b) const{ if(st != b.st) return st < b.st; else return dir < b.dir; } }; vector<Node> vec; multiset<ll> mts; int n; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ ll l, r, t; scanf("%lld%lld%lld", &l, &r, &t); //用vector模拟时间轴，我们在轴上要枚举的点包括某一作坊开始营业时刻，此时要讨论是否在当前作坊铸剑，某一作坊打烊时刻，此时把这个作坊移除我们的考虑范围，其他时刻，选择当前最快铸完一把剑的作坊铸剑，在input时我们需要添加作坊打烊和铸一把剑结束的时刻。 vec.pb(Node(l+t, START, t)); vec.pb(Node(r, END, t)); } ll ans, pre; ans = pre = 0; sort(vec.begin(), vec.end())// for(int i = 0; i < vec.size(); i++){ Node v = vec[i]; if(!mts.empty()){//mts维护当前营业中的所有作坊的铸剑时间 ll tmp = (v.st-pre)/(*mts.begin());//最早的铸完剑的时间，但不一定是只能铸一把 ans += tmp;//对答案做出贡献 pre += tmp*(*mts.begin());//pre记录的我们当前在时间轴的位置 } if(v.dir == END){//遍历到结束时刻，将铸剑时间从mts里移除 mts.erase(mts.find(v.len)); } else{ if(pre+v.len<=v.st){ //此时是我们在时间轴位于某个作坊开门的时刻 ans += 1; pre = v.st; } mts.insert(v.len); } } printf("%lld\n", ans); return 0; }