SSTF算法

oj:

https://codefun2000.com/p/P1269

学一个新东西

multiset

里面是排好序的

可以存重复的值

但是里面的值不能被修改 否则就不能排序了

可以用lower_bound(x)，得到multiset中大于等于x的最小的数的位置

auto ri = q.lower_bound(x)

若x比multiset中的任何数字都要大，则会返回q.end()

用*ri索引到位置上的值

upper_bound(x)则是返回大于x的最小的数的位置 其他一样的

 1 #include <iostream>
 2 #include <set>
 3 #include <algorithm>
 4 using namespace std;
 5 #define int long long
 6 const int N = 100010;
 7 typedef pair<int, int> PII;
 8 int n, m, k;
 9 PII tasks[N];
10 
11 signed main() {
12   ios::sync_with_stdio(0);
13   cin.tie(0);
14   cout.tie(0);
15   cin >> n >> m >> k;
16   for(int i = 1; i <= n; i++) {
17     cin >> tasks[i].second; // position
18   }
19   for(int i = 1; i <= n; i++) {
20     cin >> tasks[i].first; // time
21   }
22   sort(tasks + 1, tasks + n + 1); // order by time
23   int rest_tasks = n;
24   int now_pos = k;
25   int now_it = 1;
26   int now_time = 0; // record current time
27   multiset<int> q;
28   int res = 0;
29   while(rest_tasks--) {
30     bool wait = true;
31     while(now_it <= n && tasks[now_it].first <= now_time) {
32       q.insert(tasks[now_it++].second);
33       wait = false;
34     }
35     if(wait == true && q.size() == 0) {
36       now_time = tasks[now_it].first;
37       q.insert(tasks[now_it++].second);
38     }
39     int nextpos = -1;
40     int min_dist = 1e9;
41     auto ri = q.lower_bound(now_pos);
42     auto rm = ri;
43     if(ri != q.end()) { // if exist x that >= now_pos
44       min_dist = min(min_dist, *ri - now_pos);
45       nextpos = *ri;
46     }
47     if(ri != q.begin()) {
48       auto le = --ri;
49        if(min_dist >= (now_pos - *le)) {
50          min_dist = now_pos - *le;
51          nextpos = *le;
52          rm = le;
53        }
54     }
55     q.erase(rm);
56     res += min_dist;
57     now_time += m * min_dist;
58     now_pos = nextpos;
59   }  
60   cout << res << '\n';
61   return 0;
62 }