那位 ACM 高手快来看看哦？？
我做了一到ACM题目 提码是 2487 在PKU 中
我写的程序是 ：：：
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
题目的意思是：
第一行输入一个 int n ;
第2行输入一个大数b 和一个小数 c;
上面的c代表一个数组的数的个数，后第3行就输入数组
：
：
依次这样下去 要求的是数组中最少的几个数相加可以大于或等于b 然后输出 最少的个数。
比如输入：：
3
100 6
13 17 42 9 23 57 这里 57+42+23> =100 所以得到 3
99 6
13 17 42 9 23 57 57+42> =99 所以得到的是 2
1000 3
314 159 265 因为所有的加起来都不大于1000所以输出
impossible
后的到的结果是：：：
Scenario #1:
3
Scenario #2:
2
Scenario #3:
impossible
如果看不动的大哥可以到 ：：http://acm.pku.edu.cn/JudgeOnline/problem?id=2487
去看一下题目哦！！！
谢谢帮帮忙？
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <iostream>
using namespace std;
int main()
{
int b,a,e,sum,c,f,g;
cin > > a;
int *pp = new int [a];
for(e = 1;e <= a;e++)
{
cin > > b > > c;
int *p = new int[c];
for( int d = 0;d < c;d++)
cin > > p[d];
for(int s = 0;s < c;s++)
{ f = s;
for(int j = s + 1;j <= c;j++)
if(p[f] < p[j])f = j;
if(s!=f)
{
g = p[s];
p[s] = p[f];
p[f] = g;
}
}
sum=0;
for(int h = 0;h < c; )
{
sum += p[h];
if(sum > = b)
{
pp[e]=h+1;
break;
}
h++;
if(sum < b )
{
pp[e]=0;
}
}
}
for(int i=1;i <=a;i++)
{
if(pp[i] != 0)
{
cout < < "Scenario # " < < i < < ": " < < endl;
cout < < pp[i] < < endl;
cout < < endl;
}
else
{
cout < < "Scenario # " < < i < < ": " < < endl;
cout < < "impossible " < < endl;
cout < < endl;
}
}
system( "pause ");
return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
交了后他说我 Runtime Error 我应该怎么搞才可以把它写好
改了好就也没有该出来，
那位大哥快帮帮忙哦？？？？？
[解决办法]
int *pp = new int [a];
for(e = 1;e <= a;e++)
{
cin > > b > > c;
int *p = new int[c];
for( int d = 0;d < c;d++)
cin > > p[d];
==>
int pp[a];
for(e = 1;e <= a;e++)
{
cin > > b > > c;
int p[c];
for( int d = 0;d < c;d++)
cin > > p[d];
...
看这样是否能快那么一点 ...
[解决办法]
Runtime Error
是你程序运行错误了,检查一下吧.在某些情况下会出错
[解决办法]
个人觉得还不如先排序一下,然后从大到小加一次
[解决办法]
排序。。
然后类试背包问题。，。
[解决办法]
你的程序测试不够全面,很有可能一些临界值,或一些特殊值就不对了,你看看是不是.
[解决办法]
是时间的问题，哈哈哈。因为我也碰到过。可能题目要你只用O(n)的时间。
[解决办法]
/* 给你段C的标程。排序就好了 */
#include <stdio.h>
#include <stdlib.h>
int invcmp(const void *a, const void *b)
{
if (*(int *)a > *(int *)b)
return -1;
else if (*(int *)a < *(int *)b)
return 1;
else
return 0;
}
int main()
{
int i, j;
int n, max, k, sum;
int arr[1000];
scanf( "%d ", &n);
for (i = 1; i <= n; ++i) {
scanf( "%d %d ", &max, &k);
for (j = 0; j < k; ++j) {
scanf( "%d ", &arr[j]);
}
qsort(arr, k, sizeof(arr[0]), invcmp);
sum = 0;
for (j = 0; j < k; ++j) {
sum += arr[j];
if (sum > = max)
break;
}
printf( "Scenario #%d:\n ", i);
if (j == k)
puts( "impossible ");
else
printf( "%d\n ", j + 1);
putchar( '\n ');
}
return 0;
}
[解决办法]
there is one output for each input!
it 's no use for saving all cases ' results.
you can just simply output each case 's result
following that case.
[解决办法]
关于速度：
这个问题排序了就是至多O(n log n)速度，但你不用库函数给的排序（C++用sort），非得自己写一个更低效的，只能更慢。当然，这里即使自己写一个O(n^2)的排序也能通过。
而且你也不用把所有的数据都算出来以后才输出，算一个case就输出一个case（如kgn28所说），这样更省内存，也快些。当然，这里即使把所有的cases都算出来最后输出，也能通过。
第三，速度上C++的cin、cout比C的printf、scanf还是慢一些。当然，用cout、cin也能通过。
第四，如虫子所说，用定长的数组比用new分配一个数组要快。你的错误还在于只用new分配而不delete，数据多了内存就吃不消了。
==============================================================================
但是，真正的问题是：你的程序结果就是错的。
为什么是RE的结果（注意Runtime Error是运行错误，不是超时）我不确定：或许是你最后那用多余的system( "pause ")造成的，因为这个仅仅是用于调试的语句；也或许是因为你不delete动态数组造成的内存泄漏过于严重。
你程序主要的问题是，算法写错了（看得出来你想的没什么错）。真不知道你有没有把你的代码拿题目中已经给出的三组cases测试过，你的程序输出全部都是1！当然错了。
事实上，你的排序写错了。怎么错了，你自己检查，这是基本算法。你可以改正你自己的排序，应该最好是用C++的sort()函数。
更正的代码附后。
============================================================================
#include <iostream>
#include <algorithm>
using namespace std;
// compare function for sort algorithm
bool invcmp(const int &a, const int &b)
{
return a > b;
}
int main()
{
int b, a, e, sum, c, f, g;
cin > > a;
int *pp = new int[a];
for (e = 1; e <= a; e++) {
cin > > b > > c;
int *p = new int[c];
for (int d = 0; d < c; d++)
cin > > p[d];
/* INPUT DEBUG
cout < < endl < < "INPUT debug: " < < endl;
for (int i = 0; i < c; ++i)
cout < < i < < ': ' < < p[i] < < endl;
*/
/* your OLD WRONG sort
for (int s = 0; s < c; s++) {
f = s;
for (int j = s + 1; j <= c; j++)
if (p[f] < p[j])
f = j;
if (s != f) {
g = p[s];
p[s] = p[f];
p[f] = g;
}
}
*/
sort(p, p + c, invcmp);
/* OUTPUT DEBUG
cout < < endl < < "OUTPUT debug: " < < endl;
for (int i = 0; i < c; ++i)
cout < < i < < ': ' < < p[i] < < endl;
*/
sum = 0;
for (int h = 0; h < c;) {
sum += p[h];
if (sum > = b) {
pp[e] = h + 1;
break;
}
h++;
if (sum < b) {
pp[e] = 0;
}
}
delete[] p; // WARNING!
}
for (int i = 1; i <= a; i++) {
if (pp[i] != 0) {
cout < < "Scenario # " < < i < < ": " < < endl;
cout < < pp[i] < < endl;
cout < < endl;
} else {
cout < < "Scenario # " < < i < < ": " < < endl;
cout < < "impossible " < < endl;
cout < < endl;
}
}
delete[] pp; // it 's not necessary, but a good habbit
return 0;
}
[解决办法]
哦！用VC调试的时候才发现你RE的问题了，你的pp数组越界了！
你的下标竟然是从1开始的，不知道是从哪儿学的。这样一来上面的程序整个就要再改了，你自己弄吧。真是的……
