大师作文网C语言问题,提供思路就行（当然有伪代码甚至完整代码就更好了）
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/11 05:03:48
C语言问题,提供思路就行（当然有伪代码甚至完整代码就更好了）
In every summer there are students graduating from school.A lot of graduating students would like to host their parties to say good-bye to their classmates and friends.This kind of activity is called "bg" on our BBS.
Attending different parties will give you different feelings.You may assign each party a degree of happiness which is a non-negative integer that shows how you feel about attending to that party.
Now you are given a list of parties containing the length of each party and the time on which the host will be leaving school.It would be nice to schedule the parties so that you can obtain maximum of happiness.Since there could be as many as 30 parties on the list,you'll need the computer to help you.
Input Specification:
Your program must read test cases from standard input.
The input file consists of several test cases.Each case starts with an integer N ( 30),then followed by N lines each in the format
h l t
where h is the degree of happiness,l is the length of the party (in hours),and t is the hours after which the host will be leaving the school.It is guaranteed that l is no greater than t,since if the host will leave at the end of the t-th hour,the party will have to end by that time.
The input is finished by a negative N.
Output Specification:
For each test case,your program must output to standard output.First print in one line the maximum degree of happiness.In the next line print a possible schedule in the format:
i1 i2 ...ik
where i1 i2 ...ik are the index numbers of the parties (start counting from 1).
Note:once you select a party,you must join the party from the beginning to the end.The time taken to run from one party to another can be omitted.
In case that the solutions are not unique,output any one of them will do.
Sample Input:
4
5 1 1
10 2 3
6 1 2
3 1 1
-1
Sample Output:
16
3 2
In every summer there are students graduating from school.A lot of graduating students would like to host their parties to say good-bye to their classmates and friends.This kind of activity is called "bg" on our BBS.
Attending different parties will give you different feelings.You may assign each party a degree of happiness which is a non-negative integer that shows how you feel about attending to that party.
Now you are given a list of parties containing the length of each party and the time on which the host will be leaving school.It would be nice to schedule the parties so that you can obtain maximum of happiness.Since there could be as many as 30 parties on the list,you'll need the computer to help you.
Input Specification:
Your program must read test cases from standard input.
The input file consists of several test cases.Each case starts with an integer N ( 30),then followed by N lines each in the format
h l t
where h is the degree of happiness,l is the length of the party (in hours),and t is the hours after which the host will be leaving the school.It is guaranteed that l is no greater than t,since if the host will leave at the end of the t-th hour,the party will have to end by that time.
The input is finished by a negative N.
Output Specification:
For each test case,your program must output to standard output.First print in one line the maximum degree of happiness.In the next line print a possible schedule in the format:
i1 i2 ...ik
where i1 i2 ...ik are the index numbers of the parties (start counting from 1).
Note:once you select a party,you must join the party from the beginning to the end.The time taken to run from one party to another can be omitted.
In case that the solutions are not unique,output any one of them will do.
Sample Input:
4
5 1 1
10 2 3
6 1 2
3 1 1
-1
Sample Output:
16
3 2
首先,好像数据的格式是 权重（happiness）开始时间、结束时间.题中所说的聚会主办者离开学校的时间好像跟本题无关.按这种理解,测试数据能通过,如果按题目说的权重、持续时间、可能的结束时间的话,测试数据产生的结果就不是16 3 2
程序编制的思路大致如下：
先对聚会做个排序,按开始时间从早到晚排序,如果时间相同,权重大的往前排.然后从第一个聚会开始找出所有可能的组合并记录.可能的组合指的是时间不冲突,也就是对于一个组合,其任意两个聚会,排在前面的聚会的结束时间要不晚于排在后面的那个聚会的开始时间,然后计算总权重,如果比现有的总权重高,就替换.
P[]是保存聚会数组
p[]排序
main（）{
structure { int h int l int t int ID} as party ID是聚会的识别号,按读入数据的先后顺序依次编号.
定义堆栈结构,包含两个成员,一个是聚会,一个是一个整数,这个整数用位置来代替,用 push pop来进行进出栈操作.
定义当前解决方案结构,我们用数组S来表示,同时用v来表示这个解决方案的总权重
for（i=0；i
程序编制的思路大致如下：
先对聚会做个排序,按开始时间从早到晚排序,如果时间相同,权重大的往前排.然后从第一个聚会开始找出所有可能的组合并记录.可能的组合指的是时间不冲突,也就是对于一个组合,其任意两个聚会,排在前面的聚会的结束时间要不晚于排在后面的那个聚会的开始时间,然后计算总权重,如果比现有的总权重高,就替换.
P[]是保存聚会数组
p[]排序
main（）{
structure { int h int l int t int ID} as party ID是聚会的识别号,按读入数据的先后顺序依次编号.
定义堆栈结构,包含两个成员,一个是聚会,一个是一个整数,这个整数用位置来代替,用 push pop来进行进出栈操作.
定义当前解决方案结构,我们用数组S来表示,同时用v来表示这个解决方案的总权重
for（i=0；i