xuptoj 1298: 找到最大的乘积

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; }