Untitled
#include <iostream> #include <cmath> using namespace std; typedef long long ll; int a[100002]; ll lamtron(ll a, ll b){ // lam tron len int c = a / b; if(c < 1.0 * a / b) c++; return c; } int main() { // input int n, k; cin >> n >> k; // tinh tong ll sum = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; sum += a[i]; } ll res = 1, s = sum; //1 ngay n toa tang ll t, can, tang = 1ll * n * k; t = tang; // max toa_n ll toa_n = lamtron(1ll*a[n], 1ll*k); a[0] = a[n+1] = 0; // duyet cac doan i -> n -> xu li toa n for(int i = 1; i <= n; i++){ sum -= a[i-1]; // tong doan can = lamtron(sum, tang); toa_n = min(toa_n, can); tang -= k; } // duyet cac doan 1 -> i -> xu li tong so ngay tat ca day for(int i = n; i >= 1; i--){ s -= a[i+1]; // tong doan can = lamtron(s, t); res = max(res, can); t -= k; } cout << toa_n << " " << res; return 0; } /* 4 2 = 8 1 2 4 6 = 13 -> 13/8 = 1,... -> 2 vay toa 6 day trong toi da 2 ngay it nhat trong min(min, ?); */
Leave a Comment