CodeForces 231C To Add or Not to Add

昨天比赛的尺取题，稍微看了一下尺取算法的原理就很好理解了。

貌似可用尺取法解决的问题，二分都可以做，在复杂度上就不清楚了……

一开始也是想用二分的，感觉有点难想……

不过老实说，这道尺取对我现在来说还有有点难想到需要排序尺取……

题意：
给你很多桶水，再给你一缸水，要你从一缸水中将水补给到其他水桶中，要求相同水量的数目最多，在此条件下，水量最少。

思路：
若要水量相同，同时花费最少，那么显然在差距最小的水桶间加水。所以排序+尺取。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int n, k;
    ll sum = 0;
    pair<int, int> ans = make_pair(0, 0);
    scanf("%d %d", &n, &k);
    each(i, n) scanf("%d", ary + i);
    sort(ary, ary + n);
    for (int i = 0, j = 0; i < n; i++) {
        sum += ary[i];
        while ((i - j + 1LL) * ary[i] - sum > k)
            sum -= ary[j++];
        if (ans.second < i - j + 1LL)
            ans = make_pair(ary[i], i - j + 1LL);
    }
    printf("%d %d\n", ans.second, ans.first);
    return 0;
}