标题：乘积最大
给定N个整数A1, A2, ... AN。请你从中选出K个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。
注意，如果X<0， 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
即：0-((0-x) % 1000000009)
【输入格式】
第一行包含两个整数N和K。
以下N行每行一个整数Ai。
对于40%的数据，1 <= K <= N <= 100
对于60%的数据，1 <= K <= 1000
对于100%的数据，1 <= K <= N <= 100000 -100000 <= Ai <= 100000
【输出格式】
一个整数，表示答案。
【输入样例】
5 3
-100000
-10000
2
10000
100000
100001
【输出样例】
999100009
再例如：
【输入样例】
5 3
-100000
-100000
-2
-100000
-100000
【输出样例】
-999999829
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
思路：双指针；1.sort排序这N个数 2.使用两个指针：最左left，最右right 3.左边2个2个选 右边1个1个选（因为乘积要最大，贪心选，不能是负数（除非特殊情况）
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,k;
int a[100010];
int b[100010];
int main(){
cin>>n>>k;
int l = 1;
int r = n;
int t = 1;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
while(t<=n && l<r){
if(a[l] * a[l+1] > a[r] * a[r-1] && t+1<=k){
b[t++] = a[l];
b[t++] = a[l+1];
l+=2;
}else{
b[t++] = a[r];
r--;
}
}
for(int i=1;i<=k;i++){
cout<<b[i]<<endl;
}
}
ps：没有测试大数据，朋友们如果有做蓝桥杯题目的网站，欢迎下方评论区留言！
方法二dfs求出所有全排列，再选取乘积最大的，求余数（大数过不了）：
#include<iostream>
#include<algorithm>
#define ppp 1000000009
using namespace std;
/*思路：枚举所有组合(选取k个数) 再求出各组的乘积 取最大值*/
int n,k;
int arr[100010];
int ans[100010];
int vis[100010];
long long final[100010];
int t = 0;
//大数乘法，乘法这里有问题 求余的地方不对 什么时候该求余？
long long cheng(int ans[]){
long long sum = 1;
for(int i=0;i<k;i++){
int flag = 0;
long long ansLocal = ans[i];
if(ans[i]<0){
flag = 1;
ansLocal = -ansLocal;
}
sum = ((sum%ppp) * (ansLocal%ppp) )%ppp;
if(flag) sum = -sum;
}
return sum;
}
long long cheng2(int ans[]){
long long sum = 1;
for(int i=0;i<k;i++){
int flag = 0;
sum*= ans[i];
}
return sum;
}
//-100000 -10000 100000 999100009
//-100000 -10000 2 999999991
void dfs(int x){
if(x==k){
//计算ans中k个值的乘积处以1000000009
long long answer = cheng2(ans);
// 999999991
// if(answer == 999999991){
// for(int j = 0; j < k; j++){
// cout<<"jjj = "<<j<<" "<<ans[j]<<endl;
// }
// }
final[t++] = answer;
return;
}
for(int i=0;i<n;i++){
if(!vis[i]){
vis[i] = 1;
ans[x] = arr[i];
dfs(x+1);
vis[i] = 0;
}
}
}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>arr[i];
vis[i] = 0;
}
dfs(0);
sort(final,final+t);
for(int i=0;i<t;i++){
cout<<i<<" "<<final[i]<<endl;
}
cout<<final[t-1]%ppp<<endl;//结果和题目中的输出样例不符合
return 0;
}