[Codeforces] 477 D. Resource Distribution
題目連結:http://codeforces.com/contest/967/problem/D
只有兩個要處理的服務,所以就會猜是某種單調性或前綴或後綴之類的,通常是先O(N)或O(nlgn)之類的預處理前或後綴去處理其中一個,再O(N)或O(nlgn)處理剩下的之類的吧?
只有兩個要處理的服務,所以就會猜是某種單調性或前綴或後綴之類的,通常是先O(N)或O(nlgn)之類的預處理前或後綴去處理其中一個,再O(N)或O(nlgn)處理剩下的之類的吧?
#include<bits/stdc++.h> #define debug(a) cout << #a << " = " << a << endl; #define pb push_back #define int long long #define all(v) (v).begin(),(v).end() using namespace std; typedef pair<int,int> pi; int n,x1,x2; pi c[300009]; vector<int> ans1,ans2; signed main() { cin >> n >> x1 >> x2; for(int i = 0; i < n; i++) { cin >> c[i].first; c[i].second = i; } sort(c,c+n); int maxu = 1e9; bool ok = 0; int dd; for(int i = n-1; i >= 0; i--) { int ddd = x2/c[i].first; if(x2%c[i].first != 0) ddd += 1; if(n-i >= ddd) { dd = ddd; maxu = i; ok = 1; break; } } for(int i = 0; i < n && ok; i++) { int kk = x1/c[i].first; if(x1%c[i].first != 0) kk += 1; if(kk+i >= n) continue; if(kk+i <= maxu) { cout << "Yes" << endl; cout << kk << " " << dd << endl; for(int j = i; j < kk+i; j++) ans1.pb(c[j].second); sort(all(ans1)); for(int j = maxu; j < n; j++) ans2.pb(c[j].second); sort(all(ans2)); for(auto j:ans1) cout << j+1 << " "; cout << endl; for(auto j:ans2) cout << j+1 << " "; cout << endl; return 0; } } swap(x1,x2); ok = 0; for(int i = n-1; i >= 0; i--) { int ddd = x2/c[i].first; if(x2%c[i].first != 0) ddd += 1; if(n-i >= ddd) { dd = ddd; maxu = i; ok = 1; break; } } for(int i = 0; i < n && ok; i++) { int kk = x1/c[i].first; if(x1%c[i].first != 0) kk += 1; if(kk+i >= n) continue; if(kk+i <= maxu) { cout << "Yes" << endl; cout << dd << " " << kk << endl; for(int j = i; j < kk+i; j++) ans1.pb(c[j].second); sort(all(ans1)); for(int j = maxu; j < n; j++) ans2.pb(c[j].second); sort(all(ans2)); for(auto j:ans2) cout << j+1 << " "; cout << endl; for(auto j:ans1) cout << j+1 << " "; cout << endl; return 0; } } cout << "No" << endl; }
留言
張貼留言