更好的阅读体验

题目概述

题目描述

给出若干木棍，每根木棍有特定的颜色和长度。问能否找到三条颜色不同的木棍构成一个三角形。 (注意这里所说的三角形面积要严格大于$0$)

输入格式

第一行给出一个整数$k$,表示颜色的种数。这k种颜色被标号为$1$至$k$。
接下来$k$行，第$i+1$描述颜色为$i$的木棍的信息。 首先一个整数$N_i$表示颜色为$i$的木棍的数量。
接下来$N_i$个整数，表示这$N_i$根木棍各自的长度。

输出格式

你的程序应该仅输出一行 如果有解，输出$6$个整数.
分别表示第一条边的颜色，第一条边的长度，第二条边的颜色，第二条边的长度， 第三条边的颜色，第三条边的长度.
这六个整数以空格分割。

如果有多组解，随便输出一组即可。
如果无解，输出$NIE$

样例输入

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

样例输出

3 8 2 9 4 12

数据范围

$$ 3 \le k \le 50 \\\\ 1 \le N_i \le 10^6 \\\\ 所有木棍的长度 \le 10^9 \\\\ 总木棍数量 \le 10^6 \\\\ $$

算法解析

题意理解

要你选择三根木棒,要求这三根木棒,颜色不同,而且可以构成三角形.

算法解析

这种题目,数据范围又大,而且只要找到任意一种合法方案,不难想到是贪心之类的乱搞算法.

首先,提取木棒信息.

1. 长度
2. 颜色

而且,在这里,长度显然是,第一关键字,因为首先要先构成三角形.

因此,我们不妨,先将,所有木棒都按长度排序

排好序后,我们发现,我们只需要在这个,木棒序列里面,找到三个不同颜色的数字
$$ 不妨设a,b,c为三根木棒的长度. \quad a < b < c \\\\ 因此我们只需要找到a+b>c的数对 $$
因为知道.
$$ a < b < c $$
那么显然,最有可能的一组就是.
$$ a_{max},b_{max} $$
因此此时,他们最有可能
$$ a+b>c $$
因此我们不妨设置如下贪心.

每次保存当前,三根颜色不同的前三大木棒

举个例子.
$$ 长度:1,2,2,3,4,5 \\\\ 颜色:x,y,y,z,z,z \\\\ $$
那么假如说,我们当前在序列最后一位,则
$$ a=第一根木棒,(1,x) \\\\ b=第三根木棒,(2,y) \\\\ c=第六根木棒,(5,z) \\\\ $$
为什么是存储前三根颜色不同的木棒,而不是前两根.

因为长度排好序了,那么最大的木棒,一定就是当前这根木棒.

感谢GXZlegand大佬

代码解析

#include <bits/stdc++.h>
const int N=1000010;
using namespace std;
int n,t,tot,s1,s2,s3;
struct node
{
    int c,l;
} a[N];
int cmp(node a,node b)
{
    return a.l<b.l;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&t);
        while(t--)
        {
            a[++tot].c=i;
            scanf("%d",&a[tot].l);
        }
    }
    sort(a+1,a+1+tot,cmp);
    //s1为第一长木棒,s2为第二长,s3为第三长
    for(int i=1; i<=tot; i++)
    {
        if(a[i].c==a[s1].c)//和最长的颜色相同,则原来最长的,变成了这根木棒
        {
            if(a[s3].l+a[s2].l>a[i].l)
            {
                printf("%d %d %d %d %d %d\n",a[s3].c,a[s3].l,a[s2].c,a[s2].l,a[i].c,a[i].l);
                return 0;
            }
            s1=i;//最长的变了
        }
        else if(a[i].c==a[s2].c)//和次长的颜色相同
        {
            if(a[s3].l+a[s1].l>a[i].l)
            {
                printf("%d %d %d %d %d %d\n",a[s3].c,a[s3].l,a[s1].c,a[s1].l,a[i].c,a[i].l);
                return 0;
            }
            s2=s1,s1=i;//原来最长的,成为现在次长的,同时最长的,改成这根木棒
        }
        else//和最短的颜色相同,切记这里最短是,相比较其他两根
        {
            if(a[s2].l+a[s1].l>a[i].l)
            {
                printf("%d %d %d %d %d %d\n",a[s2].c,a[s2].l,a[s1].c,a[s1].l,a[i].c,a[i].l);
                return 0;
            }
            s3=s2,s2=s1,s1=i;//次长的成为最短,最长的成为了次长,最短成为了最长
        }
    }
    puts("NIE");
    return 0;
}