P3528 PAT-Sticks(2022.10.2)

· · 题解

题目描述：戳这里

题目大意：

  1. 给你 k 种颜色的木棍，每种木棍颜色不一样。

  2. 找出三根颜色不一样的木棍组成三角形。

  3. 如果可以输出方案，不能输出 "NIE"。

思路：

遇事不决先看数据范围。

最多有 50 种颜色，而有 10^6 的木棍。

zhx 曾经说过如果题目中出现奇怪的数据范围要着重思考。

于是这个颜色的个数就很可疑。

下面从颜色开始入手。

如果不考虑不同种颜色，那么按长度排序，如果有解的话，那么一定有一组解，三根木棍是连续的，且长度是相近的，直接找相邻的三根木棍判断是否能构成三角形即可。

那么如果考虑同种颜色，只需要对于每种颜色开一个大根堆。

把每种颜色的木棍丢进去。

单独开一个大根堆，把每种颜色长度最大的木棍丢进去。

  1. 每次取出最长的三根木棍

  2. 如果可以组成则输出。

  3. 如果当前的三根不能组成三角形则把最长的一根丢掉，因为不可能有其他的组合和它构成三角形，把剩下的两根丢回堆中。

  4. 看看与之前那个最长的相同颜色的堆中还有没有其他的，如果有就丢入新的堆中。

  5. 重复上面步骤，直至新的堆中元素不能构成三角形，输出无解。

具体细节看代码。

下面是贴心的代码。

/*

　　　　　／＞　   フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

*/
#include<bits/stdc++.h>
using namespace std;

struct node{
    int col,len;//颜色，长度 
    bool operator < (const node &T) const {
    return len < T.len;
}
};

priority_queue<node> q[55];
priority_queue<node> a;//单独开的大根堆，保证里面的木棍颜色不一样 

long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n;

bool check(node a, node b, node c)//判断是否能构成三角形 
{
    if(a.len + b.len > c.len && a.len - b.len < c.len) return true;
    else return false;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        int x = read();
        for(int j = 1; j <= x; j++)
        {
            int y = read();
            q[i].push((node){i, y});
        }
    }

    //根据思路大模拟 

    for(int i = 1; i <= n; i++) 
    {
        if(!q[i].empty())
        {
            a.push(q[i].top()); 
            q[i].pop();
        }
    }

    //找最长的三根 

    while(!a.empty())
    {
        node x = a.top();//取出三根 
        a.pop();
        node y = a.top();
        a.pop();
        node z = a.top();
        a.pop();
        if(check(x, y, z))//能构成三角形 
        {
            cout << x.col << " " << x.len << " ";
            cout << y.col << " " << y.len << " ";
            cout << z.col << " " << z.len;
            return 0;
        }
        else//不能构成三角形 
        {
            a.push(y); 
            a.push(z);
            if(!q[x.col].empty())
            {
                a.push(q[x.col].top());
                q[x.col].pop();
            }
        }
        if(a.size() < 3)//如果小于三根则不能构成三角形 
        {
            cout << "NIE" << endl;
            return 0;
        }
    }

    return 0;
}

小结：

事出反常必有妖，一定要关注奇怪的数据范围进而抓住题目的重点。