题目描述：戳这里
题目大意：
①给你k种颜色木棍，每种木棍个数不一样。
②找出三根颜色不一样的木棍组成三角形。
③如果可以输出方案，不能输出"NIE"。
思路：
遇事不决先看数据范围
最多有50种颜色，而有1e6的木棍。
zhx曾经说过如果题目中出现奇怪的数据范围要着重思考
于是这个颜色的个数就很可疑
下面从颜色开始入手
如果不考虑不同种颜色，那么按长度排序，如果有解的话，那么一定有一组解，三根木棍是连续的，且长度是相近的，直接找相邻的三根木棍判断是否能构成三角形即可
那么如果考虑同种颜色，只需要对于每种颜色开一个大根堆
把每种颜色的木棍丢进去
单独开一个大根堆，把每种颜色长度最大的木棍丢进去
①每次取出最长的三根木棍
②如果可以组成则输出
③如果当前的三根不能组成三角形则把最长的一根丢掉，因为不可能有其他的组合和它构成三角形，把剩下的两根丢回堆中。
④看看与之前那个最长的相同颜色的堆中还有没有其他的，如果有就丢入新的堆中。
⑤重复上面步骤，直至新的堆中元素不能构成三角形，输出无解
具体细节看代码
下面是贴心的代码
/*
／＞ フ
| _ _|
／`ミ _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;
}