生日劲歌会
| 试题描述 |
|
Davs到KTV唱歌庆祝生日,他妈妈给他买单的时间是n个单位时间,但KTV不会时间到就立刻鲁莽地把正在唱的歌切掉,而是等它放完,这样消费者就会多一些唱歌时间。例如,你在还有15秒时再唱一首3分钟的歌,你就会多唱165秒。现在KTV提供了Davs喜爱的n首歌,请你为Davs安排点歌的顺序,使得Davs尽可能唱更多曲目,而且离开歌厅的时间越晚越好。曲目不能重复。(中间不能空余时间) |
| 输入 |
| 第一行包含一个正整数n,接下来的若干行,每行包含一个正整数,描述一首歌曲的时间。 |
| 输出 |
| 一行,包含两个数,依次为点播歌曲的总数目和播放歌曲的总时间 |
| 输入示例 |
| 350 120 80 79 300 75 66 84 45 |
| 输出示例 |
| 6 649 |
| 其他说明 |
| n<=10000.数字个数<=5000个 |
#includeusing namespace std; int a[10010],b[10010],c[10010],n,v; int main() { cin>>v; v--; int k=1; while(cin>>a[k]) k++; sort(a,a+k); int large=a[k-1]; for(int i=1;i<=k;i++) for(int j=v;j>=a[i];j--) if(c[j] 1 || (c[j]==c[j-a[i]]+1 && b[j]a[i])) { b[j]=b[j-a[i]]+a[i]; c[j]=c[j-a[i]]+1; } int t=v-b[v]; cout< " "< t; }