Google Kickstart 2020 Round A在c语言中的分配问题

byqmnocz  于 2022-12-03  发布在  Go
关注(0)|答案(1)|浏览(293)

我用C语言写了代码,但它似乎通过了示例案例,但当涉及到测试案例时,它显示了错误的答案。输入输入的第一行给出了测试案例的数量,T。T测试案例紧随其后。每个测试案例都以包含两个整数N和B的单行开始。第二行包含N个整数。第i个整数是Ai,第i个房子的成本。
输出对于每个测试用例,输出一行包含Case #x:y,其中x是测试案例编号(从1开始),y是您可以购买的最大房屋数量。
限制时间限制:每个测试集15秒。内存限制:1GB. 1 ≤ T ≤ 100. 1 ≤ B ≤ 105. 1 ≤ Ai ≤ 1000,对于所有i.测试集1 1 ≤ N ≤ 100.测试集2 1 ≤ N ≤ 105.样本
输入
输出量
3 4 100 20 90 40 90 4 50 30 30 10 10 3 300 999 999 999
案例1:2案例2:3例病例3:0例
在范例1中,您的预算为100结雅。您可以用20 + 40 = 60结雅购买第一栋和第三栋房子。在范例2中,您的预算为50结雅。您可以用30 + 10 + 10 = 50结雅购买第一栋、第三栋和第四栋房子。在范例3中,你有300美元的预算。2你不能买任何房子(所以答案是0)。
我的密码是

#include <stdio.h>

int main(){
    int test;
    scanf("%d",&test);
    for(int i=1;i<=test;i++){
        int N;
        long int B;
        scanf("%d %ld",&N,&B);
        long int Case = 0,r=0;
        int array[10000];
        char ch;
        do {
            scanf("%d%c",&array[r],&ch);
            r++;
        }while(ch!='\n');
        for (int k=0;k<N;k++){
            for (int m=k;m<N;m++){
                int temp;
                if(array[k]>array[m]){
                    temp=array[k];
                    array[k]=array[m];
                    array[m]=temp;
                }
            }
        }
        r=0;
        while(Case<=B){
            Case+=array[r];
            r++;
        }
        printf("Case #%d: %d\n",i,r-1);
    }
}
zkure5ic

zkure5ic1#

主要原因是控制下面while循环的条件

while(Case<=B){ /* the logic of condition expression is wrong*/
   Case+=array[r];
   r++;
}

它必须是(r < N && Case+array[r]<=B)r<N是必要的;您还必须检查数组索引)。

printf("Case #%d: %d\n",i,r-1);

也是错误的。必须更正为

printf("Case #%d: %ld\n",i,r);

另一个错误是int array[10000];中的数组大小。该大小必须是100000,因为N的值最大可以是100000
您的排序算法太慢。应该使用更快的算法或标准库函数qsort

相关问题