Pavel and Triangles

发表于 分类于 ，

    给出$a_0, a_1, \cdots, a_{n-1}$，分别代表你有$a_i$根长度为$2^i$的棍子。

    现在你要将这些棍子组成尽可能多的面积大于0的三角形。

Pavel and Triangles

Created by LXC on Mon Jul 24 14:57:42 2023

https://codeforces.com/problemset/problem/1119/E

ranting: 1900

tag: brute force, dp, fft, greedy, ternary search

problem

给出$a_0, a_1, \cdots, a_{n-1}$，分别代表你有$a_i$根长度为$2^i$的棍子。

现在你要将这些棍子组成尽可能多的面积大于0的三角形。

solution

由于棍子是二的幂次，我们不可能选三种不同长度的棍子。

所以我们只能组成等腰三角形或等边三角形。

我们由小到大选择棍子长度，对于当前的长度的棍子选择两根与比它短的未匹配的进行组合。直到未匹配的棍子不够或者当前的棍子不够则停止匹配，如果则当前剩余的棍子还足够多则可以组成等边三角形。最后剩余的则给后续的棍子匹配。

code

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

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    ll ans = 0, p = 0, u = 0;
    for (int i = 0; i < n; i++) {
        cin >> u;
        if (u >= 2 * p) {
            ans += p;
            u -= 2 * p;
            ans += u / 3;
            p = u % 3;
        } else {
            ans += u / 2;
            p -= u / 2;
            p += u % 2;
        }
    }
    cout << ans << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}