首页 > ACM题库 > HDU-杭电 > HDU 3040-Happy Girls-模拟-[解题报告]HOJ
2014
02-27

HDU 3040-Happy Girls-模拟-[解题报告]HOJ

Happy Girls

问题描述 :

These days, Hunan TV host the big concert � Happy Girls.
Long1 and xinxin like it very much, they even use their cellphones to suppose the girl who they like most. This way is easy if you have enough money then you can make a contribution toward your lover.
But sometimes, it also causes the problem of injustice. Those who has a lot of money can support their lover in every second. So now, we make a rule to restrict them � every tel-number can just support once in one minute (i.e two messages should have difference bigger or equal 60s).
As an exerllent programer, your mission is to count every Happy girl’s result.

输入:

There are many cases.
For every case:

The first line gives N, represents there are N happy gilrs numbered form 1 to N(N<=10)
Then many lines follows(no more than 50000), each line gives the time one sent his/her message, the cellphone number and the number he/she support. They are sepatated by space.
The last line an message “#end”.

输出:

There are many cases.
For every case:

The first line gives N, represents there are N happy gilrs numbered form 1 to N(N<=10)
Then many lines follows(no more than 50000), each line gives the time one sent his/her message, the cellphone number and the number he/she support. They are sepatated by space.
The last line an message “#end”.

样例输入:

4
0:12:25 13854241556 1
0:15:52 15825422365 2
0:15:56 15825422365 3
0:18:55 13625415457 2
11:12:2 13954215455 4
5:41:55 13625415457 2
#end

样例输出:

The result is :
01 : *
02 : ***
03 : 
04 : *

刚开始用字典树写死活就是过不去。后来模拟的G++提交能AC,C++提交就wa。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 50005
struct node
{
	int x;
	__int64 tt;
	int id;
}a[N],b[N];
int mark[15];
int fun(char *s)
{
	int a,b,c;
	sscanf(s,"%d:%d:%d",&a,&b,&c);
	return a*3600+b*60+c;
}
int cmp(const void *a,const void *b)
{
	node *c,*d;
	c=(node *)a;d=(node *)b;
	if(c->tt!=d->tt)
		return c->tt<d->tt?1:-1;
	else
		return c->x-d->x;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,j,k;
		j=0;
		char s[15];
		while(scanf("%s",s),strcmp(s,"#end")!=0)
		{
			a[j].x=fun(s);
			scanf("%I64d%d",&a[j].tt,&a[j].id);
			j++;
		}
		qsort(a,j,sizeof(a[0]),cmp);
		k=1;
		b[0]=a[0];
		for(i=1;i<j;i++)
		{
			if(a[i].tt!=a[i-1].tt||a[i].x-a[i-1].x>=60)
				b[k++]=a[i];
		}
		memset(mark,0,sizeof(mark));
		for(i=0;i<k;i++)
			mark[b[i].id]++;
		printf("The result is :\n");
		for(i=1;i<=n;i++)
		{
			printf("%02d : ",i);
			for(j=1;j<=mark[i];j++)
				printf("*");
			printf("\n");
		}
	}
	return 0;
}

参考:http://blog.csdn.net/zizaimengzhongyue/article/details/10040343


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge