首页 > 其他分享 >洛谷P3528 [POI2011] PAT-Sticks && 数据结构之堆

洛谷P3528 [POI2011] PAT-Sticks && 数据结构之堆

时间:2024-08-20 18:06:25浏览次数:13  
标签:颜色 Sticks int POI2011 长度 heap 木棍 PAT 三角形

传送门: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

相关文章

  • [Design Pattern] Memento Pattern
    //memento.jsimport{TodoList}from"./classes.js";exportconstTodoHistory={history:[],push(state){if(state){//alwayspushanewSettoavoidreferenceissuesthis.history.push(newSet([...state]));}......
  • PAT乙级1032 || 挖掘机技术哪家强(C示例)
    挖掘机技术哪家强为了用事实说明挖掘机技术到底哪家强,PAT组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。输入格式:输入在第1行给出不超过105的正整数N,即参赛人数。随后N行,每行给出一位参赛者的信息和成绩,包括其所代表的学校的编号(从1开......
  • DriveInfo类,Path类
    DriveInfo类DriveInfo类用于获取有关驱动器(如硬盘驱动器、软盘驱动器、CD-ROM驱动器等)的信息。//获取所有逻辑驱动器的信息Drive驱动DriveInfo[]drives=DriveInfo.GetDrives();foreach(DriveInfodriveindrives){Console.WriteLine($"Drive:{drive.Name}"......
  • 微带贴片天线(microstrip patch antenna)
    基本结构:微带贴片天线是由介质基片、辐射贴片和接地板构成。设计参数主要包括贴片的材料,尺寸,工作频率。(1)贴片尺寸:微带贴片天线的尺寸影响其性能,如增益、频率等。(2)材料:介电常数表示了电介质电容器电容与真空电容器电容的比率,它在宏观上表示出这种绝缘材料储存电能能力的大小......
  • Paths和Files
    Paths类Paths类主要用于操作文件和目录路径。它提供了一些静态方法,用于创建java.nio.file.Path实例,代表文件系统中的路径。//创建一个Path实例,表示当前目录下的一个文件Pathpath=Paths.get("example.txt");//创建一个绝对路径PathabsolutePath=Paths.get("/home/u......
  • 设计模式---构建者模式(Builder Pattern)
    构建者模式(BuilderPattern)是一种创建型设计模式,旨在将复杂对象的构建过程与其表示分离。它允许使用相同的构建过程创建不同的表示。该模式通常用于构建复杂对象,这些对象由多个部分组成或具有多个可选属性。构建者模式的核心要素:Builder(构建者):定义构建对象的接口,声明创建部......
  • [20240815]oracle21c环境变量ORACLE_PATH与SQLPATH(windows).txt
    [20240815]oracle21c环境变量ORACLE_PATH与SQLPATH(windows).txt--//我记忆以前测试过这个问题,当时是家里的笔记本,安装oracle12.2cforwindows.OS:windows7,发现无法访问SQLPATH或者--//ORACLE_PATH环境变量定义的路径下login.sql文件.我当时解决办法就是登录手工执行init.sq......
  • [20240816]oracle21c环境变量ORACLE_PATH与SQLPATH(linux).txt
    [20240816]oracle21c环境变量ORACLE_PATH与SQLPATH(linux).txt--//我记忆以前测试过这个问题,当时是家里的笔记本,安装oracle12.2cforwindows.OS:windows7,发现无法访问SQLPATH或者--//ORACLE_PATH环境变量定义的路径下login.sql文件.我当时解决办法就是登录手工执行init.sql......
  • JsonPath断言
    JsonPath断言1、Maven引入依赖<!--JsonPath依赖项--><dependency><groupId>com.jayway.jsonpath</groupId><artifactId>json-path</artifactId><version>2.7.0</version>......
  • Python - Structural Design Patterns
    •TheadapterpatternTheadapterpatternisastructuraldesignpatternthathelpsusmaketwoincompatibleinterfaces compatible.Whatdoesthatreallymean?Ifwehaveanoldcomponentandwewanttouseitinanew system,oranewcomponentthatwew......