大师作文网求pascal贪心题目：线段覆盖——程序；
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/10/01 18:17:33
求pascal贪心题目：线段覆盖——程序；
请按照以下思路编写程序：首先说一下,我第一次见到这道题是在百度noip贴吧的一位吧友共享的《基本程序题集》中.在该吧友给出的题解中这样写到：“贪心策略为从左到右,每次选取线段右端点坐标最小的线段.保留这条线段,并把和这条线段有公共部分的所有线段删除.证明：因为右端点坐标最小,可保证所有与这条线段没有公共部分的线段都在这条线段的右边,且所有与这条线段有公共部分的线段两两之间都有公共部分,而右端点坐标最小的线段对后面的线段影响最小.”如果直接写出这样的程序,语言和循环会很乱.我做了以下优化.1、读入数据时对于左端点相同的点,只保留右端点最小的.2、没必要“删除线段”之类的.用一个变量统计剩下线段数就行了.3、优化存储结构,不用二维数组存每条线段左右端点,改用一维数组.具体请见“程序”中第一条.程序：1、读入数据.用一个1..2000的数组road【k】储存线段信息.对于k属于1~2000,road[k]的值代表左端点为k的线段右端点的值.{这样做是为了省掉排序并降低空间复杂度}2、选择“当前剩下的线段中 左端点最小的那条线段”.若没有线段了就结束.3、从该线段左端点遍历至右端点,若 其中没有其他线段的右端点,则总线段数+1,从当前线段右端点继续遍历（执行步骤2）；否则记录其他线段右端点中最小的一个,总线段数+1,并从这个最小右端点的线段的右端点开始继续遍历（执行步骤2）.4、输出总线段数.这样做貌似是2重循环O(n^2)的复杂度,实际上最多只可能循环2000+100次；只用了一个一维数组1..2000,空间复杂度为O(m).因此我的程序只用了1MS就通过了.
PS：求完整代码,后期有附加加分,若有注释,
请按照以下思路编写程序：首先说一下,我第一次见到这道题是在百度noip贴吧的一位吧友共享的《基本程序题集》中.在该吧友给出的题解中这样写到：“贪心策略为从左到右,每次选取线段右端点坐标最小的线段.保留这条线段,并把和这条线段有公共部分的所有线段删除.证明：因为右端点坐标最小,可保证所有与这条线段没有公共部分的线段都在这条线段的右边,且所有与这条线段有公共部分的线段两两之间都有公共部分,而右端点坐标最小的线段对后面的线段影响最小.”如果直接写出这样的程序,语言和循环会很乱.我做了以下优化.1、读入数据时对于左端点相同的点,只保留右端点最小的.2、没必要“删除线段”之类的.用一个变量统计剩下线段数就行了.3、优化存储结构,不用二维数组存每条线段左右端点,改用一维数组.具体请见“程序”中第一条.程序：1、读入数据.用一个1..2000的数组road【k】储存线段信息.对于k属于1~2000,road[k]的值代表左端点为k的线段右端点的值.{这样做是为了省掉排序并降低空间复杂度}2、选择“当前剩下的线段中 左端点最小的那条线段”.若没有线段了就结束.3、从该线段左端点遍历至右端点,若 其中没有其他线段的右端点,则总线段数+1,从当前线段右端点继续遍历（执行步骤2）；否则记录其他线段右端点中最小的一个,总线段数+1,并从这个最小右端点的线段的右端点开始继续遍历（执行步骤2）.4、输出总线段数.这样做貌似是2重循环O(n^2)的复杂度,实际上最多只可能循环2000+100次；只用了一个一维数组1..2000,空间复杂度为O(m).因此我的程序只用了1MS就通过了.
PS：求完整代码,后期有附加加分,若有注释,
program ex1214;vara:array[1..100,1..2]of longint;f:array[1..100]of longint;n,i,j,k:longint;function max(x,y:longint):longint;begin if x>y then max:=x else max:=y; end;//较大值函数procedure readd;var p:longint;beginreadln(n);for i:=1 to n dobeginreadln(a[i,1],a[i,2]);if a[i,1]>a[i,2] then begin p:=a[i,1]; a[i,1]:=a[i,2]; a[i,2]:=p; end;end;for i:=1 to n do f[i]:=1;end;//读入数据procedure sort;var p:array[1..2]of longint;beginfor i:=1 to n-1 do for j:=i+1 to n doif a[i,1]>a[j,1] then begin p:=a[i]; a[i]:=a[j]; a[j]:=p; end;end;//排序procedure work;beginfor i:=n-1 downto 1 do for j:=i+1 to n doif a[i,2]k then k:=f[i];//for i:=1 to n do writeln(a[i,1],' ',a[i,2],' ',f[i]);writeln(k);end;//工作部分beginreadd;sort;work;end.//主程序
再问： ��ã��ҿ�����ij�������ֶ������ˣ��ܷ�work�������ؽ���һ�£�Ҫ��ϸ�������ȫ��û��������һ��work˼·��лл��
再答： ����ܷ��5�죬�����ĩ��
再问： ��ã��ҿ�����ij�������ֶ������ˣ��ܷ�work�������ؽ���һ�£�Ҫ��ϸ�������ȫ��û��������һ��work˼·��лл��
再答： ����ܷ��5�죬�����ĩ��