程序设计语言综合设计解题报告（一）

题目（一）：

航船游戏中，风向每个单位时间会改变一次，每次航船可以选择顺风前行一个单位距离，也可以选择原地不动。游戏时长为 t，请你计算从起点出发，最终到达终点所需要的最少移动次数。如果游戏结束也到达不了终点，则输出-1。

输入格式:

第一行包括一个正整数 t（1<=t<=100000）。

第二行为起点坐标（x1 , y1）。

第三行为终点坐标（x2 , y2）。

接下来 t 行，每行输入一个单词，表示风向 。

输出格式:

输出为一个整数，为到达终点所需移动的最少步数；如果无法到达，输出-1。

分析（解题思路及流程图）：

1、 如果最短需要移动次数（横纵坐标差的绝对值相加）比可移动次数还小，则必不可能到达重点，输出-1，直接结束程序

2、 分析题目可知，如果风向与目标方向相反则不用移动，相同则可以选择移动。所以先确认移动方向（通过始末坐标）

3、 通过for循环获取每次移动的方向，利用四个方向起始字母不同只要获取第一个字母就ok了

4、 用两个变量统计在输入风向中和目标方向相同的风向的出现次数（表述不太清楚 见代码）

5、 判断能否到达终点（见代码）如果能的话输出最短次数，不能的话输出-1

程序核心代码（或伪代码）：

#include<stdio.h>
#include<math.h>
int main()
{
	int n,x1,y1,x2,y2;
	scanf("%d",&n);
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	if(abs(x1-x2)+abs(y1-y2)>n)
	{
		printf("-1");
		return 0;
	}
	char dir1,dir2;
	int cnt1=0,cnt2=0;
	if(x1>x2)
	dir1='w';
	else if(x1==x2)
	dir1='N';
	else
	dir1='e';
	if(y1>y2)
	dir2='s';
	else if(y1==y2)
	dir2='N';
	else
	dir2='n';
	for(int i=1;i<=n;i++)
	{
		char d[8];
		scanf("%s",d);
		if(d[0]==dir1)
		cnt1++;
		else if(d[0]==dir2)
		cnt2++;
	}
	if(cnt1>=abs(x1-x2)&&cnt2>=abs(y1-y2))
	printf("%d",abs(x1-x2)+abs(y1-y2));
	else
	printf("-1");
	return 0;
}

心得：

手生的不行，太久没有打C语言代码了，寒假习惯python了有点转不过来，打了几题才稍微有点手感，我觉得只取首字母判断方向还是比较妙的，比较简单也不用用循环来判断字符串是否相等（python就比较容易判断qwq），只要能达到目的能“偷懒”就尽量偷懒叭，只判断首字母减少了很多工作量

题目（二）：

设有n个任务，其中每个任务有一个起始时间si和一个结束时间ei，且si<ei，同一时间只能完成一个任务。如果选择了任务i ，则它在时间区间 [si ,ei) 内占用资源。若区间 [si ,ei) 与区间 [sj, ej)不相交，则称任务 i 与任务 j 是相容的。那么，对于给定的任务时间区间，能互相兼容的最大任务个数是多少呢？

输入格式:

第一行一个整数n （1<=n<=1000） ；

接下来n行，每行两个整数si 和 ei。

输出格式:

互相兼容的最大任务个数。

分析（解题思路及流程图）：

分析：这题和上学期那题集装箱的感觉有点点像，我的思路是从最小的开始填，因为长度为四的区间可以装一段长度为四的任务也可以装四段长度为一的任务（大致是这个意思）

流程：

1、 读取数据，存入结构体数组

2、 排序，将用时最长的排在结构体最后

3、 定义一个整型数组，初始值均为0

4、 从结构体数组中获取始末时间，如果时间区间内数组值均为0，将时间区间的数组值设为1，让计数器加一；如果不满足则跳过这一个任务

5、 输出计数器的值

6、 因为非常奇妙的原因在PTA上编译失败，Dev上能跑，代码应该没啥问题

程序核心代码（或伪代码）：

#include<stdio.h>
int main()
{
	int n;
	scanf("%d",&n);
	int len=0;//max len
	struct WORK
	{
		int s;
		int e;
		int l;
	}a[n+1],t;
	int count=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].s,&a[i].e);
		a[i].l=a[i].e-a[i].s+1;
		if(a[i].l>len)
		len=a[i].l;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n-i;j++)
		{
			if(a[i].l>a[i+1].l)
			{
				t=a[i];
				a[i]=a[i+1];
				a[i+1]=t;
			}
		}
	}
	int flag[n+1]={0};
	for(int i=1;i<=n;i++)
	{
		int f=1;
		for(int j=a[i].s;j<a[i].e;j++)
		{
			if(flag[j]==1)
			{
				f=0;
				break;
			}
		}
		if(f==1)
		{
			for(int k=a[i].s;k<a[i].e;k++)
			flag[k]=1;
			count++;
		}
	}
	printf("%d",count);
	return 0;
}

心得：qsort还是用不好，最后还是选择用冒泡，qsort再琢磨琢磨