传送门:P3528 [POI2011] PAT-Sticks
与买桂花同载酒,终不似,少年游
这是现在为止洛谷上的最优解!!
翻译
题目描述
小约翰尼的爷爷奶奶送给他一份生日礼物。
这份礼物是一盒长度和颜色各异的木棍。
约翰尼想知道,在他得到的这组木棍中,是否存在三根木棍能够组成一个三边颜色各不相同的三角形。
输入格式
在标准输入的第一行,给定一个整数 k( 3 ≤ k ≤ 50 ),它表示木棍的不同颜色数量。
颜色本身从 1 到 k 编号。
接下来的 k 行包含特定颜色木棍的描述。
第 i+1 行包含描述颜色 i 木棍的整数,这些整数之间用单个空格分隔。
这些数中的第一个 n ( 1 ≤ n ≤ 1000000 ),表示颜色为 i 的木棍的数量
紧接着有 n 个整数,表示颜色 i 木棍的长度。所有长度都是正数,并且不超过 1 000 000 000。
此外,所有木棍的总数不超过 1 000 000。
输出格式
你的程序应该在标准输出的第一行(也是唯一一行)上打印以下内容之一:
六个整数,用单个空格分隔,描述了一个由三边颜色各不相同的木棍组成的三角形的构造,具体格式如下:
- 第一根木棍的颜色和长度
- 第二根木棍的颜色和长度
- 第三根木棍的颜色和长度
如果不存在这样的三根木棍可以组成一个三角形,则打印单词“NIE”(波兰语中的“不”)。
如果有多组颜色各不相同的木棍可以组成三角形,你的程序可以任意选择其中一组进行输出。
请注意,约翰尼只对非退化三角形(即面积为正的三角形)感兴趣。
题目意思:
给出 n 根木棍的颜色和长度,问你是否能找到三根颜色不同的木棍组成三角形。
如果可以,输出任意一种方案,否则输出“NIE”
思路:
- 假设所有木棍的颜色都不一样
维护一个大根堆,将所有木棍的长度扔进堆里,每次取堆中第一个、第二个和第三个元素,如果他们不能组成三角形,那么就没有木棍能与第一根组成三角形,可以将堆顶丢掉。
证明:因为这种情况下保证了堆里所有元素的颜色不同,所以我们只需要考虑木棍的长度。
设上面选出的三个木棍的长度分别为 a,b,c。( a >= b >= c )
他们要组成三角形的条件是:a < b + c
如果不满足,说明 a >= 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;
}
标签:颜色,Sticks,int,POI2011,长度,heap,木棍,PAT,三角形
From: https://www.cnblogs.com/lazy-ZJY0307/p/18369728