CF1991F Triangle Formation

Tag：思维、三角形

题目描述

给定 \(n\) 个木棍，第 \(i\) 根木棍的长度为 \(a_i\)。给 \(q\) 次查询，每次查询给定 \(l,r(1 \leq l \le r \leq n,r - l + 1 \geq 6)\)，判断这个区间内是否存在六个木棍可以组成两个非退化三角形。

其中非退化三角形指的是任意两边之和大于第三边，不能相等。

数据说明： \(6 \le n \le 10^5\), \(1 \le q \le 10^5\), \(1 \le a_i \le 10^9\)

分析

首先，一个三角形成立的条件是任意两边之和大于第三边。

我们先想一下如果要找一个三角形怎么做，这里有一个结论：

我们可以将长度排序，之后遍历每一个相邻的三元组，如果这些三元组都无法组成一个三角形，那么这些长度就不存在一个能构成三角形的三元组。

所以我们可以把每次查询的区间进行排序之后看相邻的三元组能否组成三角形，但是问题在于题目没有保证 \(q\) 次查询的区间长度和，如果每次都选了整个数组，每次都排序的时间复杂度是无法接受的。

我们进一步考虑一下是否有办法能够快速的确定一个区间能否组成一个三角形。我们先尝试构建一个无解的边长数组，我们可以采用形如 \(\{1,1,2,3,5,8,13\cdots\}\) 的构造方案，这样一来一定无法组成三角形了。我们可以发现这种构造方案是一个斐波那契数列，于是我们考虑这样在题目给定的 \(a_i\) 值域中最多可以构造多少项，计算之后发现第 \(45\) 项超过了值域范围。

由此我们得出结论：

当区间长度 \(\geq 45\) 时，一定能存在三个长度构成一个三角形。

我们把这个结论推广到两个三角形，就是区间长度 \(\geq 48\) 时一定可以构成两个。因为 \(48\) 个一定能构成一个三角形，我们去掉这三个边，剩下的边有 \(45\) 个，依然可以构成一个。

于是我们对于区间长度大于等于 \(48\) 的查询直接输出可以，对于剩余的区间我们就可以暴力寻找是否能构造出两个三角形，具体方法如下：

首先查找是否存在一组 \(i,j\)，其中\((i + 2 \le j)\)，满足 \(a_i + a_{i+1} \ge a_{i+2}\) 并且 \(a_j + a_{j+1} \ge a_{j+2}\)，如果存在，则可以构成。如果不存在，有可能是这两个三元组在排序之后混到一起了，所以我们判断是否存在一个 \(i\)，使得 \(a_i,a_{i+1},a_{i+2},a_{i+3},a_{i+4},a_{i+5}\) 能构成两个三角形，至于如何判断这部分，我们直接暴力枚举判断多写几个 \(if\) 就可以了。

感性理解上面这一部分，其实六个连续的组成两个三角形，是从两个分开的连续的组成的三角形转移而来的，因为连续的三个如果可以组成一个三角形，我们存在两个这样的区间，由于我们对长度进行排序了，这一部分有概率是交叉到一起的。比如两组分别是 \(a_i,a_{i+1},a_{i+2}\) 和 \(a_j,a_{j+1},a_{j+2}\)，我们排序之后可能会产生形如 \(\{a_i,a_i+1,a_j,a_j+1,a_i+2,a_j+2\}\)，这种两个区间混到了一起不再连续的情况，而实质上如果我们从这六个中匹配了一组三角形，并且把这三条边删掉之后，剩下的可以构成另一个三角形的边依然是连续的。正是因为存在上述情况，我们才需要判断一下连续的六个是否可以组成两个三角形。

代码实现

void NeverSayNever() {
    int n, q; cin >> n >> q;
    vector<int> vec(n);
    for (auto &x: vec) cin >> x;
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (r - l + 1 >= 48) {
            cout << "YES" << endl;
            continue;
        }
        bool flag = false;
        vector<int> tmp(vec.begin() + l - 1, vec.begin() + r);
        std::sort(tmp.begin(), tmp.end());
        int L = 1e9,R = -1;
        for (int i = 0; i + 2 < tmp.size(); ++i) {
            if(tmp[i] + tmp[i + 1] > tmp[i + 2]){
                L = min(L,i);
                R = i;
            }
        }
        if(R - L >= 3){
            cout << "YES" << endl;
            continue;
        }
        for (int i = 0; i + 5 < tmp.size(); i++) {
            if (tmp[i] + tmp[i + 1] > tmp[i + 3] && tmp[i + 2] + tmp[i + 4] > tmp[i + 5]) {
                flag = true;
                break;
            }
            if (tmp[i] + tmp[i + 1] > tmp[i + 4] && tmp[i + 2] + tmp[i + 3] > tmp[i + 5]) {
                flag = true;
                break;
            }
            if (tmp[i] + tmp[i + 2] > tmp[i + 3] && tmp[i + 1] + tmp[i + 4] > tmp[i + 5]) {
                flag = true;
                break;
            }
            if (tmp[i] + tmp[i + 2] > tmp[i + 4] && tmp[i + 1] + tmp[i + 3] > tmp[i + 5]) {
                flag = true;
                break;
            }
            if (tmp[i] + tmp[i + 3] > tmp[i + 4] && tmp[i + 1] + tmp[i + 2] > tmp[i + 5]) {
                flag = true;
                break;
            }
            if (tmp[i + 1] + tmp[i + 2] > tmp[i + 3] && tmp[i] + tmp[i + 4] > tmp[i + 5]) {
                flag = true;
                break;
            }
            if (tmp[i + 1] + tmp[i + 2] > tmp[i + 4] && tmp[i] + tmp[i + 3] > tmp[i + 5]) {
                flag = true;
                break;
            }
        }
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

额外思考

感觉排序判相邻看是否能组成三角形是一个可能很常见的结论，这下学到了。

日志

本页面创建于 2024/7/30 20:12