题目链接
题意就是给你一堆线段，然后线段有长度和颜色，让你选三条组成一个三角形，这三条线段颜色不能一样
题解：
做法：贪心
首先按照长度给这些线段排序一遍
然后贪心的去选，对于已经选出来同种颜色的，就拿它去替换同种颜色
不然就替换最小的
这样都能为后面创造更多的选择
复杂度$O(n)$
#include <bits/stdc++.h> #define ll long long
#define inf 0x3f3f3f3f
#define il inline #define in(a) a=read()
#define out(a) printf( "%d" , a )
#define outn(a) out(a),putchar('\n') #define I_int int
inline I_int read() { I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) {
if( c == '-' ) f = - ;
c = getchar() ;
}
while( c >= '' && c <= '' ) {
x = (x << ) + (x << ) + c - ;
c = getchar() ;
}
return x * f ;
}
#undef I_int using namespace std ; #define N 1000100 int n , k = read() ;
struct node {
int val , col ;
bool operator < ( const node &x ) const {
return val < x.val ;
}
} a[ N ] , b[ ] ; int main() {
for( int i = ; i <= k ; i ++ )
for( int j = , m = read() ; j <= m ; j ++ )
a[ ++ n ].col = i , a[ n ].val = read() ;
sort( a + , a + n + ) ;
for( int i = ; i <= n ; i ++ ) {
bool flag = ;
for( int j = ; j < ; j ++ )
if( !flag && a[ i ].col == b[ j ].col )
b[ j ].val = a[ i ].val , flag = ;
if( !flag ) b[ ] = a[ i ] ;
sort( b , b + ) ;
if( b[ ].col && b[ ].val + b[ ].val > b[ ].val ) {
for( int j = ; j < ; j ++ )
printf( "%d %d " , b[ j ].col , b[ j ].val );
return ;
}
}
puts("NIE") ;
return ;
}