【作业向】程序设计思维与实践 Week10 限时大模拟

发表于 | 分类于 ，
字数统计: 1.8k | 阅读时长 ≈ 9

【作业向】程序设计思维与实践 Week10 限时大模拟

♔A 签到题

这是真·签到题，若读入的三个数中有偶数，则可以平均分配，直接输出0；若没有偶数则无法平均分配，为了差距最小，则输出三个数中较小的两个数的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#define ll long long
using namespace std;
ll a[4];

int main()
{
	ll i,j;
	for(i=1;i<=3;i++) scanf("%lld",&a[i]);
	sort(a+1,a+4);
	if(a[1]%2==0 || a[2]%2==0 || a[3]%2==0) printf("0");
	else printf("%lld",a[1]*a[2]);
	return 0;
}

♔B 团队聚会

这一题还是比较考验代码能力和思维能力的，我的做法是将读入的事件拆开，分成开始和结束两个事件，并记录是事件类型及所属的队员，然后按时间进行排序。排好序后检查开头的事件是否是1800/01/01 00:00:00，若不是则加入一个时间为1800/01/01 00:00:00的空事件；然后检查结尾的事件是否为2200/01/01 00:00:00，若不是则加入一个时间为2200/01/01 00:00:00的空事件。然后再进行排序（这样写常数可能大了一些）。

接下来进行一次遍历，若一个事件不与上一个事件时间重复，则加入到时间队列中；若时间重复则跳过（奇怪的常数增加了）。然后定义数组visit[i] [j],若为一，则表示第i个人在第j个时间有事情，这一个我们通过类似于前缀和的方法来处理。处理完成后需要再处理出visit[0] [j]表示在第j个时间有visit[0] [j]个人有事情，至此处理的部分就完成了。

然后进行求解，一个时间满足要求的条件是在该时段有事情的人要小于等于一，且总人数减去有事情的人数大于等于总人数减1。又因为时间段要尽可能的长，因此我们需要找的起点是连续一段满足条件的时间段中的第一个时间段，终点是连续一段满足条件的时间段后的第一个不满足条件的时间段。

然后判断是否大于等于一小时，这里都转化为秒来计算。又因为每个月只有30天，所以无法使用ctime中自带的函数进行转换。我的方法是，对于时间a和b（a早于b），t等于b的年减去a的年，t自乘12，t等于t+b的月减a的月，然后t自乘30，t等于t+b的天减a的天，，，以此类推就可以算出b比a晚多少秒，若t大于等于3600秒，则符合要求，则进行输出，否则继续遍历。

由此可见，这个做法的时间复杂度主要是在排序上，总的时间复杂度是O(Tmnlog(mn))还是比较优秀的。

image-20200425155942723

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<ctime>
#define ll long long
using namespace std;
struct data
{
	int n,y,r,s,f,m;
	int peo,flg,pti;
}pe[5000],pep[5000];
int T,n,m,pcnt,psum,pre,pt;
int visit[25][5000];
char c[50000];

int wly(data a,data b)
{
	if(a.n<b.n) return 1;
	else if(a.n==b.n)
	{
		if(a.y<b.y) return 1;
		else if(a.y==b.y)
		{
			if(a.r<b.r) return 1;
			else if(a.r==b.r)
			{
				if(a.s<b.s) return 1;
				else if(a.s==b.s)
				{
					if(a.f<b.f) return 1;
					else if(a.f==b.f)
					{
						if(a.m<b.m) return 1;
						else if(a.m==b.m)
						{
							if(a.flg<b.flg) return 1;
							else if(a.flg==b.flg)
							{
								if(a.peo<b.peo) return 1;
							}
						}
					}
				}
			}
		}
	} 
	return 0;
}

int judge(data a,data b)
{
	ll tim=0;
	tim=b.n-a.n;
	tim*=12;
	tim=(b.y+tim)-a.y;
	tim*=30;
	tim=(b.r+tim)-a.r;
	tim*=24;
	tim=(b.s+tim)-a.s;
	tim*=60;
	tim=(b.f+tim)-a.f;
	tim*=60;
	tim=(b.m+tim)-a.m;
	if(tim>=3600) return 1;
	else return 0;
}

int main()
{
	//freopen("in_ff","r",stdin);
	//freopen("a1.txt","w",stdout);
	int i,j,k,h;
	scanf("%d",&T);
	for(h=1;h<=T;h++)
	{
		pcnt=0;
		psum=0;
		pt=0;
		memset(pe,0,sizeof(pe));
		memset(pep,0,sizeof(pep));
		memset(visit,0,sizeof(visit));
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&m);
			for(j=1;j<=m;j++)
			{
				++pcnt;
				scanf("%4d%2d%2d%2d%2d%2d",&pe[pcnt].n,&pe[pcnt].y,&pe[pcnt].r,&pe[pcnt].s,&pe[pcnt].f,&pe[pcnt].m);
				pe[pcnt].peo=i;pe[pcnt].flg=0;
				++pcnt;
				scanf("%4d%2d%2d%2d%2d%2d",&pe[pcnt].n,&pe[pcnt].y,&pe[pcnt].r,&pe[pcnt].s,&pe[pcnt].f,&pe[pcnt].m);
				pe[pcnt].peo=i;pe[pcnt].flg=1;
				//c=getchar();
				//while(c!='\n') c=getchar();
				gets(c);
			}
		}
		//printf("%d-----\n",pcnt);
		sort(pe+1,pe+1+pcnt,wly);
		if(!(pe[pcnt].n==2200 && pe[pcnt].y==1 && pe[pcnt].r==1 && pe[pcnt].s==0 && pe[pcnt].f==0 && pe[pcnt].m==0))
			pe[++pcnt].n=2200;pe[pcnt].y=1;pe[pcnt].r=1;pe[pcnt].flg=1;
		if(!(pe[1].n==1800 && pe[1].y==1 && pe[1].r==1 && pe[1].s==0 && pe[1].f==0 && pe[1].m==0))
			pe[++pcnt].n=1800;pe[pcnt].y=1;pe[pcnt].r=1;pe[pcnt].s=0;pe[pcnt].f=0;pe[pcnt].m=0;
		sort(pe+1,pe+1+pcnt,wly);
//		for(i=1;i<=pcnt;i++)
//		{
//			printf("-%d- %4d %2d %2d %2d %2d %2d %2d\n",visit[0][i],pe[i].n,pe[i].y,pe[i].r,pe[i].s,pe[i].f,pe[i].m,pe[i].peo);
//		}
		pep[++psum]=pe[1];
		pe[1].pti=psum;
		for(i=2;i<=pcnt;i++)
		{
			if(pe[i].n==pe[i-1].n && pe[i].y==pe[i-1].y && pe[i].r==pe[i-1].r && pe[i].s==pe[i-1].s && pe[i].f==pe[i-1].f && pe[i].m==pe[i-1].m)
			{
				if(pe[i].peo==pe[i-1].peo && pe[i].flg==pe[i-1].flg) continue;
				pe[i].pti=psum;
			}
			else
			{
				pep[++psum]=pe[i];
				pe[i].pti=psum;
			}
		}
		for(i=1;i<=pcnt;i++)
		{
			if(pe[i].peo==0) continue;
			if(pe[i].flg) visit[pe[i].peo][pe[i].pti]-=1;
			else visit[pe[i].peo][pe[i].pti]+=1;
		}
//		for(i=1;i<=pcnt;i++)
//		{
//			for(j=1;j<=n;j++) printf("%d ",visit[j][i]);			
//			printf("\n");
//		}
		for(i=1;i<=n;i++) 
			for(j=1;j<=psum;j++) visit[i][j]+=visit[i][j-1];
//		printf("-------\n"); 
//		for(i=1;i<=pcnt;i++)
//		{
//			for(j=1;j<=n;j++) printf("%d ",visit[j][i]);			
//			printf("\n");
//		}
		for(i=1;i<=psum;i++) 
			for(j=1;j<=n;j++) if(visit[j][i]) visit[0][i]+=1;
		visit[0][psum]=n;
//		for(i=1;i<=pcnt;i++)
//		{
//			printf("-%d- %4d %2d %2d %2d %2d %2d %2d\n",visit[0][i],pe[i].n,pe[i].y,pe[i].r,pe[i].s,pe[i].f,pe[i].m,pe[i].peo);
//		}
		printf("Scenario #%d:\n",h);
		pre=1;
		while(pre<=psum && (visit[0][pre]>1 || n-visit[0][pre]<2)) pre++;
		//printf("---%d---\n",pre);
		for(i=pre+1;i<=psum;i++)
		{
			if(visit[0][i]<=1 && n-visit[0][i]>=2) continue;
			if(judge(pep[pre],pep[i])) 
			{
				printf("appointment possible from %02d/%02d/%04d %02d:%02d:%02d to %02d/%02d/%04d %02d:%02d:%02d\n",pep[pre].y,pep[pre].r,pep[pre].n,pep[pre].s,pep[pre].f,pep[pre].m,pep[i].y,pep[i].r,pep[i].n,pep[i].s,pep[i].f,pep[i].m);
				pt=1;
			}	
			while(i<=psum && (visit[0][i]>1 || n-visit[0][i]<2)) i++;
			pre=i;
		}
		if(!pt) printf("no appointment possible\n");
		printf("\n");
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！