#include <algorithm> #include <cstdio> #include <vector> using namespace std; int search(vector<int> growth, int begin, int end, long long day, long long h); int main() { int n, m, tmp; scanf("%d %d\n", &n, &m); vector<int> growth; for(int i=0; i<n; i++) { scanf("%d ", &tmp); growth.push_back(tmp); } sort(growth.begin(), growth.end()); vector<long long> combined_growth; combined_growth.push_back(0); for(int i=0; i<n; i++) { combined_growth.push_back(growth[i]+combined_growth[i]); } long long day, h, prev = 0, result; int index; for(int i=0; i<m; i++) { scanf("%lld %lld\n", &day, &h); if(day*growth[0] >= h) index = -1; else if(day*growth.back() <= h) index = n-1; else index = search(growth, 0, n-1, day, h); index++; result = day*(combined_growth.back()-combined_growth[index]) - h*(n-index) - prev; if(result < 0) result = 0; prev += result; printf("%lld\n", result); } return 0; } int search(vector<int> growth, int begin, int end, long long day, long long h) { if(end-begin < 2) { if(day*growth[end] <= h) return end; else return begin; } int mid = (begin + end)/2; if(day*growth[mid] <= h) return search(growth, mid, end, day, h); else return search(growth, begin, mid, day, h); }
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 55 56 57 58 59 | #include <algorithm> #include <cstdio> #include <vector> using namespace std; int search(vector<int> growth, int begin, int end, long long day, long long h); int main() { int n, m, tmp; scanf("%d %d\n", &n, &m); vector<int> growth; for(int i=0; i<n; i++) { scanf("%d ", &tmp); growth.push_back(tmp); } sort(growth.begin(), growth.end()); vector<long long> combined_growth; combined_growth.push_back(0); for(int i=0; i<n; i++) { combined_growth.push_back(growth[i]+combined_growth[i]); } long long day, h, prev = 0, result; int index; for(int i=0; i<m; i++) { scanf("%lld %lld\n", &day, &h); if(day*growth[0] >= h) index = -1; else if(day*growth.back() <= h) index = n-1; else index = search(growth, 0, n-1, day, h); index++; result = day*(combined_growth.back()-combined_growth[index]) - h*(n-index) - prev; if(result < 0) result = 0; prev += result; printf("%lld\n", result); } return 0; } int search(vector<int> growth, int begin, int end, long long day, long long h) { if(end-begin < 2) { if(day*growth[end] <= h) return end; else return begin; } int mid = (begin + end)/2; if(day*growth[mid] <= h) return search(growth, mid, end, day, h); else return search(growth, begin, mid, day, h); } |