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 }
标签:tasks,dist,min,int,算法,now,SSTF,ri From: https://www.cnblogs.com/i-rong/p/17444728.html