传送门

参考了钟浩曦的讲解，但对于证明的地方可能更加详细。

题目意思：

给出每根木棍的颜色和长度，问你是否能找到三根颜色不同的木棍组成三角形。如果可以，输出任意一种方案，否则输出 "NIE"。

思路：

首先我们要知道一个数据结构：

堆

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于或小于等于其父亲的键值。每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。

以上来自 OIWIKI。

堆是一种支持插入、查询最值、删除最值、合并的数据结构。

• 大根堆

主要用来查询最大的元素，删除最大元素。

STL 中的优先队列（priority_queue）实际上就是一个大根堆。

下面是大根堆的几种操作：

#include<queue>

priority_queue<int>heap;

int main()
{
	heap.push(x); //插入元素
	heap.empty(); //判断是否为空 
	heap.top(); //访问堆顶元素
	heap.size(); //查询元素数量
	heap.pop(); //删除堆顶元素 
}

• 小根堆

主要用来查询最小元素，删除最小元素。

这里提供一种用 priority_queue 实现小根堆的方法：

我们只要在插入和查询最值的时候取相反数就行了，其他与大根堆相同。

当然，使用 greater、重载运算符都是可以的。

假设所有木棍的颜色都不一样

维护一个大根堆，将所有木棍的长度扔进堆里，每次取堆中第一个、第二个和第三个元素，如果他们不能组成三角形，那么就没有木棍能与第一根组成三角形，可以将堆顶丢掉。

证明： 因为这种情况下保证了堆里所有元素的颜色不同，所以我们只需要考虑木棍的长度。设上面选出的三个木棍的长度分别为 $a$，$b$，$c$（$a \ge b \ge c$）。他们要组成三角形的条件是：$a < b + c$。如果不满足，说明 $a \ge b + c$。又因为大根堆中保证了元素是不上升的，接下来选择的 $b$ 和 $c$ 一定小于等于原来的 $b$ 和 $c$，绝对不会再满足条件，此时将 $a$（堆顶）丢掉即可。

考虑正解

在上一种情况中，我们发现：只要堆中没有颜色相同的木棍，那么上一种方法就可行。那么我们可以：

对于每一种颜色，建一个大根堆；

每次只取每个大根堆中的堆顶元素放入总的大根堆；

每次将总的大根堆的堆顶扔掉时，再向堆里扔一个同颜色的堆的堆顶；（这样保证同一时刻的堆中没有颜色相同的木棍）

直到找到一组解。

代码：

要注意的点都写在代码里了。

#include<bits/stdc++.h>

using namespace std;

int k,n;
int len;

priority_queue<int>Heap[55];
 //Heap[i]中存储颜色为 i 的木棍长度 
priority_queue<pair<int,int> >heap;
 //pair 的 first 存储 木棍的长度，pair 的 second 存储木棍的颜色 

int main()
{
	scanf("%d",&k);
	for(int i = 1;i <= k;i ++)
	{
		scanf("%d",&n);
		for(int j = 1;j <= n;j ++)
		{
			scanf("%d",&len);
			Heap[i].push(len);
		}
	}
	for(int i = 1;i <= k;i ++)
	 //先把每种颜色的木棍中最长的放入总的堆中 
	{
		if(! Heap[i].empty())
		{
			int lens = Heap[i].top();
			heap.push({lens,i});
			Heap[i].pop();
		}
	}
	while(heap.size() >= 3) //开始查找 (注意，这里的条件是堆中木棍数量 >= 3 )
	{
		int a = heap.top().first,a_i = heap.top().second;
		heap.pop();
		int b = heap.top().first,b_i = heap.top().second;
		heap.pop();
		int c = heap.top().first,c_i = heap.top().second;
		if(a < b + c){
			printf("%d %d %d %d %d %d",a_i,a,b_i,b,c_i,c);
			return 0;//找到了一组合法解，结束 
		}
		heap.push({b,b_i});
		if(! Heap[a_i].empty())
		{
			int lens = Heap[a_i].top();
			heap.push({lens,a_i});
			Heap[a_i].pop();
		}
	}
	printf("NIE");
	return 0;
}