BZOJ_2529_[Poi2011]Sticks_贪心
Description
Little Johnny was given a birthday present by his grandparents. This present is a box of sticks of various lengths and colours. Johnny wonders if there are three sticks in the set he has been given that would form a triangle with different-coloured sides. Let us note that Johnny is interested in non-degenerate triangles only, i.e., those with positive area.
给出若干木棍，每根木棍有特定的颜色和长度。问能否找到三条颜色不同的木棍构成一个三角形。
(注意这里所说的三角形面积要严格大于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
Sample Input
4
1 42
2 6 9
3 8 4 8
1 12
1 42
2 6 9
3 8 4 8
1 12
Sample Output
3 8 4 12 2 9
首先按长度排序。
对于构成三角形有一个很显然的贪心，这三条边的长度要尽可能的接近。
现在有了颜色的限制，我们处理出nxt[i]表示i的颜色这一段连续的末尾位置。
然后枚举最短的那条边，中间那条就一定是最短边的下一个颜色的最后一个，因为最短和最长的固定后中间的边显然越长越好。
然后枚举最长边的颜色，要满足大于等于最短边且长度最小，容易发现这个是单调的。
总时间复杂度$O(nk)$。能过就行。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define RR register
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd() {
RR int x=0; RR char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
#define N 1000050
vector<int>v[55];
int n,K,num[55],nxt[N],pos[55];
struct A {
int col,v;
}a[N];
bool cmp(const A &x,const A &y) {
return x.v<y.v;
}
int main() {
K=rd();
int i,j;
for(i=1;i<=K;i++) {
num[i]=rd();
for(j=1;j<=num[i];j++) {
a[++n].col=i;
a[n].v=rd();
}
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++) {
v[a[i].col].push_back(i);
}
int now=0;
for(i=n;i>=1;i--) {
if(a[i].col!=a[now].col) {
nxt[i]=i; now=i;
}else {
nxt[i]=now;
}
}
int x,y,z;
for(i=1;i<=n;i++) {
// printf("col=%d,v=%d,nxt[i]=%d
",a[i].col,a[i].v,nxt[i]);
int x=i,y=nxt[nxt[i]+1];
if(y==0) continue;
for(j=1;j<=K;j++) {
if(j!=a[x].col&&j!=a[y].col&&pos[j]<num[j]) {
while(pos[j]<num[j] && a[ v[j][pos[j]] ].v<a[x].v) {
pos[j]++;
}
if(pos[j]>=num[j]) continue;
z=v[j][pos[j]];
if(a[x].v+a[y].v>a[z].v) {
printf("%d %d %d %d %d %d
",a[x].col,a[x].v,a[y].col,a[y].v,a[z].col,a[z].v); return 0;
}
}
}
}
puts("NIE");
}