GroupBlog

1298: 找到最大的乘积

时间限制: 1 Sec 内存限制: 128 MB
提交: 64 解决: 6
[ 提交][ 状态][ 讨论版]

题目描述

给定N(N < 100)个数，每个数的绝对值小于等于5，从这N个数中找到M个数，使得这M个数的乘积最大，请你输出最大的乘积

输入

第一行一个整数T, 表示询问的组数，T < 20

每组数据：

第一行两个整数N, M

第二行为N个数，中间用空格隔开

输出

求得的乘积最大值

样例输入

 2 4 4 1 2 3 4 3 3 1 2 3

样例输出

 24 6

提示

注意读题～

几组数据之间要注意初始化等问题

一道题错了6次还是7次，反正错了好多遍

刚开始都把他当做正数了，排完序之后就不停的累乘就完了。后来想到了还有负数，实际应该先比较正数的乘积和负数的乘积，如果负数的乘积大就取出两个负数，不然就取出最大正数。像我这样的渣渣就被这样坑了n次^_^

#include<stdio.h>
#include<string.h>

int a[101];

void sort(int n) {
    int i;
    int j;
    int t;
    
    for(i = 0;i < n;i++) {
        for(j = i;j < n;j++) {
            if(a[i] > a[j]) {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

int main(void) {
    int T;
    int n;
    int m;
    int sum;
    int count;
    int i;
    int j;
    
    scanf("%d",&T);
    while(T--) {
        memset(a,0,sizeof(a));
        count = 1;
        scanf("%d %d",&n,&m);
        for(i = 0;i < n;i++) {
            scanf("%d",&a[i]);
        }
        sort(n);
        i = 0;
        j = n - 1;
        
        while(i <= n - 1 && j >= 0 && m > 0) {
            if(a[i] * a[i+1] > a[j] * a[j-1] && m >= 2) {
                count *= (a[i] * a[i+1]);
                i += 2;
                m -= 2;
            } else {
                count *= a[j];
                j--;
                m--;
            }
        }
        printf("%d\n",count);
    }
    return 0;
}