Article From:



First, let’s take a look at the data range of this problem. The amount of data in Subtask 4 is 10^15 to a surprising extent. Obviously, this is the amount of data that we can not handle. But looking at the size of R is acceptable, so it is not hard to imagine that there is a discretization idea.

Then we think about how to arrange the rice barn. This rice bin is actually equivalent to a “median”, which is arranged in the middle of the section which can be processed by the rice bin.

Here is the concept of “interval”, so we can think of a similar two point idea to enumerate the left and right boundaries of the interval.

First, O (R) enumerates the left border, then inserting a while to check the right boundary, and writing a check function to check the feasibility of the interval. Check is actually using a prefix to calculate the amount of money, and then compared with the budget, return to true or false.

Card point

Here is a small card point that is data type. At the beginning, we opened the int type, but when we think about the amazing amount of 10^15 that we saw before, it is necessary to open long long.


 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 100000 + 10;
 4 long long S[MAXN], R, x[MAXN], r, b, ans, t;
 5 bool check(int Left, int Right)
 6 {
 7     int hub_pos = (Left + Right) >> 1;
 8     long long Cost=1ll*x[hub_pos]*(hub_pos-Left+1)-S[hub_pos]+S[Left-1]+S[Right]-S[hub_pos]-1ll*x[hub_pos]*(Right-hub_pos);
 9     if (Cost <= b)
10         return true;
11     return false;
12 }
13 int main()
14 {
15     freopen("","r",stdin);
16     freopen("ricehub.out","w",stdout);
17     cin >> r >> t >> b;
18     for (int i = 1; i <= r; i++)
19     {
20         cin >> x[i];
21         S[i] = S[i-1] + x[i];
22     }
23     R = 1;
24     for (int L = 1; L <= r; L++)
25     {
26         while (R <= r && check(L,R))
27             R++;
28         ans = max(ans, R-L);
29     }
30     cout << ans << endl;
31     return 0;
32 }


Link of this Article: IOI 2011 Rice Hub rice barn

Leave a Reply

Your email address will not be published. Required fields are marked *