POJ Wooden Sticks

spoiler posted @ 2011年4月08日 14:43 in Ecole Polytechnique Contest 解题报告 , 1041 阅读

题目分析:就是让你求一个坐标数组里,满足x,y同时递增的序列个数!

              拿到题目我就想到贪心,但是一直没得到很好的证明,所以一直迟迟不敢去尝试,毕竟也是比赛,呵呵,后来有人说贪心过, 突然觉得自己也许会考虑的复杂了!其实题目也没有什么最优解选择方案,只是简简单单的 x,y同时递增的序列个数。

现在就贴一下我的代码 如果您有对本题有更好的思路希望您能给我批阅!{^_^}

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;

struct node{
	int x,y;
}s[10000];

int vs[10000];

int cmp(struct node a,struct node b){
	if(a.x!=b.x)
		return a.x<b.x;
	else
		return a.y<b.y;
}

int main(){
	int cas,n,i,ans,j,t;
	cin>>cas;
	while(cas--){
		cin>>n;
		memset(vs,0,sizeof(vs));
		ans=0;
		for(i=1;i<=n;i++){
			cin>>s[i].x>>s[i].y;
		}
		sort(s+1,s+n+1,cmp);
		for(i=1;i<=n;i++){
			if(!vs[i]){
				t=s[i].y;
				ans++;
				for(j=i+1;j<=n;j++){
					if(s[j].y>=t&&vs[j]==0){
						t=s[j].y;
						vs[j]=1;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter