CodeRazer's blog

By CodeRazer, history, 19 months ago, In English

Problem

279B - Books

My approach

The total time taken to read all books is sum. Then for every iteration if the sum is greater than the free time you can either remove the first book or the last book in the series, it's better to remove the book with the higher read duration for optimal solution (It is optimal because, since we have to remove a book, it's better to remove the one with the higher read duration to have more potential time for reading other books). If there are any doubts regarding the approach, refer to the code.

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long

using namespace std;

int main(void) {
    ll n, t; cin >> n >> t;
    vector<ll> a(n);
    ll sum = 0;
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    ll lo = 0;
    ll hi = n - 1;
    while (sum > t && hi >= lo) {
        if (a[lo] > a[hi]) {
            sum -= a[lo];
            lo++;
        } else {
            sum -= a[hi];
            hi--;
        }
    }
    cout << hi - lo + 1 << endl;
}

Issue

Obviously my approach or program (or both) are incorrect, but I'm having a hard time finding what is wrong. I would appreciate any help. Thanks in advance :)

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think you understood the problem correctly. You need to choose a subarray of maximum size such that its sum does not exceed T, and that could be anywhere in the array, so you do not always take either from the front or rhe back.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The greedy approach of removing a book without looking at the whole array may not always give the correct result. Consider the example array: 4, 1, 1, 9, 3 with t = 6. The best subarray here is 4,1,1 but your algorithm eliminates 4 in the first step itself.