#include <algorithm> #include <iostream> #include <vector> using namespace std; int find_first_bigger(vector<int>& a, unsigned long long factor, unsigned long long val) { int l, r, s; l = 0; r = a.size(); unsigned long long temp; while (l != r) { s = (l + r) / 2; temp = factor * a[s]; if (temp < val) l = s+1; else r = s; } return l; } int main() { unsigned long long day, last_day, last_len, act_len, grass_weight, acc_len_diff; int n, m; vector<int> a; vector<unsigned long long> daily_growth; last_day = 0; last_len = 0; cin >> n >> m; a.resize(n); daily_growth.resize(n+1); for (int i = 0; i != n; i++) cin >> a[i]; sort(a.begin(), a.end()); daily_growth[n] = 0; for (int i = n - 1; i >= 0; i--) daily_growth[i] = daily_growth[i+1] + a[i]; for (int i = 0; i != m; i++) { int first_bigger = 0; cin >> day >> act_len; if (act_len > last_len) first_bigger = find_first_bigger(a, (day - last_day), (act_len - last_len)); acc_len_diff = (n - first_bigger) * (last_len - act_len); grass_weight = acc_len_diff + daily_growth[first_bigger] * (day - last_day); cout << grass_weight << endl; last_day = day; last_len = act_len; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <algorithm> #include <iostream> #include <vector> using namespace std; int find_first_bigger(vector<int>& a, unsigned long long factor, unsigned long long val) { int l, r, s; l = 0; r = a.size(); unsigned long long temp; while (l != r) { s = (l + r) / 2; temp = factor * a[s]; if (temp < val) l = s+1; else r = s; } return l; } int main() { unsigned long long day, last_day, last_len, act_len, grass_weight, acc_len_diff; int n, m; vector<int> a; vector<unsigned long long> daily_growth; last_day = 0; last_len = 0; cin >> n >> m; a.resize(n); daily_growth.resize(n+1); for (int i = 0; i != n; i++) cin >> a[i]; sort(a.begin(), a.end()); daily_growth[n] = 0; for (int i = n - 1; i >= 0; i--) daily_growth[i] = daily_growth[i+1] + a[i]; for (int i = 0; i != m; i++) { int first_bigger = 0; cin >> day >> act_len; if (act_len > last_len) first_bigger = find_first_bigger(a, (day - last_day), (act_len - last_len)); acc_len_diff = (n - first_bigger) * (last_len - act_len); grass_weight = acc_len_diff + daily_growth[first_bigger] * (day - last_day); cout << grass_weight << endl; last_day = day; last_len = act_len; } } |