主题:[讨论]这题谁给我讲个方法?
盒子的操作问题【box.pas】
[问题描述]
St_venp最近接到了一个烦人的任务。他有n个容量有限的盒子,同时还有一个容量无限大的超级盒子。这n个盒子都被编上了号,从1号到n号。现在有些盒子里有东西,有些盒子是空的。这个超级盒子里也有一些东西。
现在他的任务就是,要对这些盒子进行操作,实际上就是把盒子里的东西拿来拿去。有一个叫ZZZZ的人需要他盒子里的东西,但是St_venp的盒子太多了,ZZZZ不可能把所有盒子都带走,于是ZZZZ在St_venp完成任务后,只会把他的超级盒子带走。ZZZZ需要在带走超级盒子时,超级盒子里至少有k单位的东西。
St_venp可以进行的操作有两种:
(1)F i j操作:从超级盒子里拿j单位的东西放到i号盒子里。
(2)D i操作:把i号盒子里的东西全部放回超级盒子里。
然而,并不是所有的操作都可以进行,当某个操作符合下面三个条件之一时,它就不会进行:
(1)执行F操作时,i号盒子放不下了。
(2)执行F操作时,超级盒子里的东西不够了。
(3)执行D操作时,i号盒子已经空了。
除此之外,所有的操作都会进行。
操作严格按顺序进行,即对于两条可以进行的操作,前面的操作一定在后面的操作之前进行。
St_venp实在不知道怎么操作,就向他的同事求助,没想到几天以后同事给他一个写满了操作的纸。St_venp不想进行那么多操作,就向删掉一些,但是他又不想花太多的时间在删操作上,于是他想删掉的操作尽可能少,又能满足ZZZZ的要求。
请问最少删掉哪几条操作?
[输入文件]
输入文件box.in的第一行有两个数,表示操作前超级盒子里的东西数量和盒子数n。
第二行n个数,第i个数表示i号盒子的容量。(1<=所有数<=10000)
第三行n个数,第i个数表示在操作前i号盒子里的东西数量,空盒子为0。
第四行两个数,表示纸上的操作数s和ZZZZ的需求量k。
最后s行,每行描述一条操作。
(限制:
1<=n<=1000
1<=s<=2000
1<=k<=MAXLONGINT
)
[输出文件]
输出文件box.out的第一行有一个数x,表示最少要删掉的操作数。
接下来x行每行一个数,表示要删掉的操作编号。
如果无论怎么删也没办法达到ZZZZ的要求,则输出一个"N"。
[输入样例1]
10 5
8 8 7 8 7
1 0 2 0 5
5 15
F 1 3
F 2 8
F 2 7
D 1
D 5
[输出样例1]
1
3
[输入样例2]
1 2
5 5
0 5
3 10
F 1 1
D 1
D 2
[输出样例2]
N
[补充说明]
在任何时候,超级盒子里的东西数量都不会超过MAXLONGINT。
[问题描述]
St_venp最近接到了一个烦人的任务。他有n个容量有限的盒子,同时还有一个容量无限大的超级盒子。这n个盒子都被编上了号,从1号到n号。现在有些盒子里有东西,有些盒子是空的。这个超级盒子里也有一些东西。
现在他的任务就是,要对这些盒子进行操作,实际上就是把盒子里的东西拿来拿去。有一个叫ZZZZ的人需要他盒子里的东西,但是St_venp的盒子太多了,ZZZZ不可能把所有盒子都带走,于是ZZZZ在St_venp完成任务后,只会把他的超级盒子带走。ZZZZ需要在带走超级盒子时,超级盒子里至少有k单位的东西。
St_venp可以进行的操作有两种:
(1)F i j操作:从超级盒子里拿j单位的东西放到i号盒子里。
(2)D i操作:把i号盒子里的东西全部放回超级盒子里。
然而,并不是所有的操作都可以进行,当某个操作符合下面三个条件之一时,它就不会进行:
(1)执行F操作时,i号盒子放不下了。
(2)执行F操作时,超级盒子里的东西不够了。
(3)执行D操作时,i号盒子已经空了。
除此之外,所有的操作都会进行。
操作严格按顺序进行,即对于两条可以进行的操作,前面的操作一定在后面的操作之前进行。
St_venp实在不知道怎么操作,就向他的同事求助,没想到几天以后同事给他一个写满了操作的纸。St_venp不想进行那么多操作,就向删掉一些,但是他又不想花太多的时间在删操作上,于是他想删掉的操作尽可能少,又能满足ZZZZ的要求。
请问最少删掉哪几条操作?
[输入文件]
输入文件box.in的第一行有两个数,表示操作前超级盒子里的东西数量和盒子数n。
第二行n个数,第i个数表示i号盒子的容量。(1<=所有数<=10000)
第三行n个数,第i个数表示在操作前i号盒子里的东西数量,空盒子为0。
第四行两个数,表示纸上的操作数s和ZZZZ的需求量k。
最后s行,每行描述一条操作。
(限制:
1<=n<=1000
1<=s<=2000
1<=k<=MAXLONGINT
)
[输出文件]
输出文件box.out的第一行有一个数x,表示最少要删掉的操作数。
接下来x行每行一个数,表示要删掉的操作编号。
如果无论怎么删也没办法达到ZZZZ的要求,则输出一个"N"。
[输入样例1]
10 5
8 8 7 8 7
1 0 2 0 5
5 15
F 1 3
F 2 8
F 2 7
D 1
D 5
[输出样例1]
1
3
[输入样例2]
1 2
5 5
0 5
3 10
F 1 1
D 1
D 2
[输出样例2]
N
[补充说明]
在任何时候,超级盒子里的东西数量都不会超过MAXLONGINT。