【bzoj2529】[Poi2011]Sticks 贪心

题目描述

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

输入

第一行给出一个整数k(3<=k<=50),表示颜色的种数。这k种颜色被标号为1至k。
接下来k行，第i+1描述颜色为i的木棍的信息。
首先一个整数Ni(1<=Ni<=10^6)表示颜色为i的木棍的数量。
接下来Ni个整数，表示这Ni根木棍各自的长度。
所有木棍的长度<=10^9。总木棍数量<=10^6。

输出

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

样例输入

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

样例输出

3 8 2 9 4 12

题解

贪心

三条边能够构成三角形的充要条件：两短边之和大于长边。

那么如果已知长边，要尽可能地让它与另外两条边构成三角形，所选的两条边需要尽可能的长。

所以我们可以先按长度从小到大排序，从左到右枚举长边，所需要知道的就是它之前长度最大的两条与其颜色不同的边。我们可以直接维护三条颜色不同的前三长边，然后找到这三条边中与其颜色不同的最长的两条，判断能否构成三角形，并更新这三条边即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 1000010

using namespace std;

struct data

{

	int c , l;

	bool operator<(const data &a)const {return l < a.l;}

}a[N];

int tot;

int main()

{

	int k , i , t , s1 = 0 , s2 = 0 , s3 = 0;

	scanf("%d" , &k);

	for(i = 1 ; i <= k ; i ++ )

	{

		scanf("%d" , &t);

		while(t -- ) a[++tot].c = i , scanf("%d" , &a[tot].l);

	}

	sort(a + 1 , a + tot + 1);

	for(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;

}

巴特西

【bzoj2529】[Poi2011]Sticks 贪心

最新文章

热门文章