题目链接：https://codeforces.com/problemsets/acmsguru/problem/99999/543

题目大意：有 $n$ 个团体，每张桌子有 $r$ 个位置，问最小多少张桌子能让所有人上桌，要求：一个桌子上不会出现一个团体只有一个人在这张桌子上。

做法

注意到一个事情：任何一个 $>1$ 的正整数可以被拆分成若干 $2,3$ 的和，但问题是，我们不知道每个团体的人要被拆成多少个 $2,3$ （显然，知道有多少个 $2,3$ ，就可以在足够优秀的时间复杂度内得到最少的桌子数量）。

但是又注意到一个事情：一个桌子上有两个 $3$ 和一个团体被拆分成两个 $3$ 这两件事不会同时发生，因为发生这种情况时可以交换，然后把两个 $3$ 拆成 $3$ 个 $2$ 。

因此我们只要分成两种情况讨论就行了：

  1. 每个团体至多拆出一个 $3$ 。
  2. 每个桌子至多放置一个 $3$ 。

然后讨论一下就做完了，我采用了二分，所以时间复杂度是：$O(n\log{V})$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 5;
int n, R, a[N];
namespace Solve1{//any team only one    
    bool evenpd(int res, int cnt, int num2, int num3){
        assert(res % 2 == 0);
        if(1ll * res * cnt < num2 * 2 + num3 * 3) return 0;
        if(1ll * res / 6 * 2 * cnt >= num3) return 1;
        int tmp = res % 6;
        if(tmp < 3) return 0ll;
        num3 -= 1ll * res / 6 * 2 * cnt;
        return tmp * cnt >= num3 * 4 + num2 * 2;
    }
    bool pd(int cnt, int num2, int num3){
        if(!(R & 1)) return evenpd(R, cnt, num2, num3);
        if(num3 <= cnt) return 1ll * (R - 1) * cnt >= (num2 + num3) * 2;
        else return evenpd(R - 3, cnt, num2, num3 - cnt);
    }
    int solve(){
        int num2 = 0, num3 = 0;
        for(int i = 1; i <= n; i++){
            if(a[i] & 1) num3 ++, num2 --;
            num2 += a[i] / 2;
        }
        int l = 1, r = 2000 * n, mid, ans = 0;
        while(l <= r){
            mid = (l + r) / 2;
            if(pd(mid, num2, num3)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        assert(ans);
        return ans;
    }
}
namespace Solve2{
    bool pd(int cnt, int num2, int num3, int num6){
        if(num3 > cnt) return 0;
        int use = num3 + min((cnt - num3) / 2 * 2, num6 * 2);
        return (num3 * 3 + num2 * 2 + num6 * 6 + (cnt - use)) <= 1ll * cnt * R;
    }
    int solve(){
        if(!(R & 1)) return 1e9;
        int num2 = 0, num3 = 0, num6 = 0;
        for(int i = 1; i <= n; i++){
            int tmp = a[i];
            if(a[i] & 1) num3 ++, tmp -= 3;
            num6 += tmp / 6;
            tmp %= 6;
            num2 += tmp / 2;
        }
        int l = 1, r = 2000 * n, mid, ans = 0;
        while(l <= r){
            mid = (l + r) / 2;
            if(pd(mid, num2, num3 ,num6)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        assert(ans);
        return ans;
    }
}
int main(){
    cin >> n >> R;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cout << min(Solve1::solve(), Solve2::solve()) << "\n";
    return 0;
}

还有个问题，如果知道了有多少个 $2,3$ ，可以多快知道有多少个桌子数，显然 $O(\log)$ 可以，但是可以线性吗？

我们不妨设 $f(x)$ 表示有 $x$ 张桌子的情况下，将 $3$ 的桌子放进去，最多还能放入多少的 $2$ ，而 $f$ 显然能写成 $O(1)$ 个分段函数相加，且边界可以在 $O(1)$ 的时间处理完，所以一定可以在 $O(1)$ 的时间解决，具体讨论不再赘述。

因此，每个团队至多一个 $3$ 的情况可以在 $O(1)$ 的时间内解决。

同理，每张桌子至多一个 $3$ 的情况，显然此时可以认为 $r$ 为奇数，$r$ 为偶数的情况这种情况肯定不如另一种情况优。

可以先把原来的团队分成：$0/1$ 个 $3$ ，最多的 $6$ 和剩下的 $2$。

设 $f(x)$ 表示有 $x$ 张桌子的话至多能放多少个人，其中 $x\ge 3$ 的个数，因此 $f(x)$ 关于 $x$ 是偶数和奇数分别是分段函数，因此类似上面的，只要肯讨论，也可以在 $O(1)$ 内解决。

综上，该问题可以在 $O(n)$ 时间内解决。