P3528 [POI2011]PAT-Sticks 题解

题目传送门

[POI2011]PAT-Sticks

题目描述

给你每根木棍的长度和颜色,求一个能拼成三角形且木棍颜色互不相同的方案

输入格式

第一行输入一个整数 $k(3 \le k \le 50)$ ,表示一共有多少种不同的颜色。

颜色从 $1$ 到 $k$ 编号。接下来的 $k$ 行表示不同颜色木棍的颜色、长度信息。

第 $i+1$ 行,有多个用单个空格分隔的整数,表示第 $i$ 种颜色木棍的信息。在这 $k$ 行的第一个数字 $n_i$ ,表示颜色为$i$的木棍的数量。每一行在读入的 $n_i$ 之后,有 $n_i$ 个整数,每个整数表示每根颜色为 $i$ 的木棍的长度。

所有木棍的长度都是整数,并且不超过 $10^9$ ,所有木棍的数量不超过 $10^6$ 。

输出格式

输出一行,包括 $6$ 个整数,用一个空格隔开,分别是选择的第一个、第二个、第三个被选择的木棍的颜色和长度。

如果不存在,输出 NIE

样例 #1

样例输入 #1

4
1 42
2 6 9
3 8 4 8
1 12

样例输出 #1

3 8 4 12 2 9

提示

给你每根木棍的长度和颜色,求一个能拼成三角形且木棍颜色互不相同的方案

题解

前言

这篇题解的讲者为:钟皓曦,我只是将钟老师的讲解整理并复述一遍。

启发

我们从简单的问题开始,假设所有的木棍颜色都是不同的,也就是说我们可以选择任意木棍来尝试着组成三角形。

zhx:

如果题目中给出的数据顺序变换不会影响最终结果的话,就去考虑对数据进行排序。

排序,设我们要找出的三根木棒的长度为 $a,b,c(a \gt b \gt c)$ ,因为 $a,b,c$ 的可以构成一个三角形,所以应该满足以下条件:

$$a \gt b \gt a-c$$

所以存在一种方法:分别查找 $a$ 和 $a-c$ 的位置,在这两个位置中间,是否可以加入 $b$ 这个数,如果有,则存在构成三角形的方法。

如何避免查找呢?那就是选择排序后三根连续的木棒进行判断,当确定 $a$ 的时候,我们去寻找尽可能小的 $a-c$ ,也就是寻找尽可能大的 $c$ ,又要去寻找尽可能大但是又不超过 $a$ 的 $b$ ,所以连续的三根木棒是极端情况最优解,所以面对所有木棍颜色都不同的情况下,从头枚举三根木棍即可得到答案,时间复杂度 $O(n)$ 。

问题解决

根据启发,我们知道,选择长度相近的三根木棒是最有肯能得到解决方案的,那么面对存在颜色相同的木棒应该如何处理?

仍然是排序,每种颜色的木棒分别排序,每次选择颜色不同的、长度最相近的三根木棒逐个判断也可以得到答案。

思路已有,如何实现?

因为我们要不断获得不同颜色木棒的长度的最长值(考虑从长到短寻找),所以使用大根堆来维护,并单独建立起一个大根堆,这个单独的大根堆中存储着当前还未排除的不同颜色的最长的木棍,每次选择最长的三根木棍进行比较,能构成三角形则输出,否则将单独建立的大根堆堆顶的木棍弹出,说明其不能和其他木棍构成符合要求三角形。被弹出的木棍属于哪种颜色,就将哪种颜色剩下木棍中最长的加入单独建立的大根堆,直到该颜色没有木棍可用,这样保证了单独建立的大根堆内所有的木棍颜色不同,并包含所有可用颜色的木棍。最终如果没有三根木棍来组成三角形,说明结果不存在。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct Node{
    int len,col;
}temp[4];
bool operator <(const Node &a,const Node &b){
    return a.len<b.len;
}
priority_queue<Node> h[50];
priority_queue<Node> q; 
int n,col[55][1000010];
int main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&col[i][0]);
        for(int j=1;j<=col[i][0];j++){
            scanf("%d",&col[i][j]);
            h[i].push({col[i][j],i});
        }
    }
    for(int i=1;i<=n;i++){
        q.push(h[i].top());
        h[i].pop();
    }
    while(q.size()>=3){
        for(int i=1;i<=3;i++){
            temp[i]=q.top();
            q.pop();
        }
        if(temp[1].len-temp[2].len<temp[3].len){
            printf("%d %d %d %d %d %d",temp[1].col,temp[1].len,temp[2].col,temp[2].len,temp[3].col,temp[3].len);
            return 0;
        }
        if(h[temp[1].col].size()){
            q.push(h[temp[1].col].top());
            h[temp[1].col].pop();
        }
        q.push(temp[2]);
        q.push(temp[3]);
    }
    printf("NIE");
    return 0;
}
文章标题:P3528 [POI2011]PAT-Sticks 题解
文章链接:https://www.laoguantx.top/p3528-poi2011pat-sticks-%e9%a2%98%e8%a7%a3.html
文章内容仅供参考,其中可能会有部分内容参考、引用其他网站,转发请务必标注作者为 “老官童鞋gogo” ,原文链接为 https://www.laoguantx.top/p3528-poi2011pat-sticks-%e9%a2%98%e8%a7%a3.html 。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇