/** * Solution to IOI 2009 problem "hiring" * * O(NlogN) solution. We process the candidates in increasing * order of "utility" (where utility is the candidate's minimum * rate of pay per unit of qualification). If we hire a candidate * with utility U, then we know that for all candidates with * utility V < U we'll be able to meet their minimum salary * requirement. This is because: * * V = S1 / Q1 < S2 / Q2 = U * => S1 < (Q1 / Q2) * S2 = the amount that candidate 1 * will get paid * * The speedup to NlogN comes from the fact that we store the * candidates qualification values in a heap, giving O(logN) * time to insert them and then O(logN) time to remove over- * qualified candidates from the heap who are inflating the * cost too much. * * Carl Hultquist, chultquist@gmail.com */ #include #include #include #include #include #include using namespace std; #define MAX_N 500000 class candidate { public: double s, q, r; int i; bool operator < (const candidate &c) const { return r < c.r; } }; candidate c[MAX_N]; int n; long long w; int best = 0; int bestIndex = 0; double bestCost = 0; int main() { scanf("%d %lld", &n, &w); assert(1 <= n && n <= MAX_N); for (int i = 0; i < n; i++) { scanf("%lf %lf", &c[i].s, &c[i].q); c[i].r = c[i].s / c[i].q; c[i].i = i + 1; } sort(c, c + n); // We now have a list of the candidates sorted by their utility. We // process the candidates in this order, and add them to the list of // candidates chosen. While the set of candidates chosen costs us // too much, we remove the most qualified candidate (and thus the one // which is inflating the cost too much). double totalQual = 0; vector heapQuals; heapQuals.reserve(n); for (int i = 0; i < n; i++) { heapQuals.push_back(c[i].q); push_heap(heapQuals.begin(), heapQuals.end()); totalQual += c[i].q; double maxQual = w / c[i].r; while (totalQual > maxQual) { totalQual -= heapQuals[0]; pop_heap(heapQuals.begin(), heapQuals.end()); heapQuals.pop_back(); } // If we have more candidates than we have previously // seen before, then make a note of the number and of // the last candidate that we processed. int num = (int) heapQuals.size(); double cost = totalQual * c[i].r; if (num > best || (num == best && cost < bestCost)) { best = num; bestCost = cost; bestIndex = i; } } // In order to maintain an O(NlogN) algorithm, we must // recreate the best set of candidates outside the main // loop (if we updated it inside the main loop, we could // trigger O(N) updates giving overall complexity of // O(N^2)! vector > heap; bool usedCandidate[n + 1]; memset(usedCandidate, 0, sizeof(usedCandidate)); totalQual = 0; for (int i = 0; i <= bestIndex; i++) { heap.push_back(make_pair(c[i].q, c[i].i)); push_heap(heap.begin(), heap.end()); totalQual += c[i].q; usedCandidate[c[i].i] = true; } // Remove over-qualified candidates double maxQual = w / c[bestIndex].r; while (totalQual > maxQual) { totalQual -= heap[0].first; usedCandidate[heap[0].second] = false; pop_heap(heap.begin(), heap.end()); heap.pop_back(); } // Output the list of candidates used printf("%d\n", best); for (int i = 1; i <= n; i++) if (usedCandidate[i]) printf("%d\n", i); return 0; }