1239. 乘积最大

https://www.acwing.com/problem/content/description/1241/
1e5的数据量,显然不能暴搜,但是我还是要暴搜

显然寄了,只能过一半数据,这题的正确做法应该分情况讨论

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e5+10;
const long long MOD = 1000000009;
int a[N],k,n;
bool used[N];
long long res=-90000000000;
void dfs(int step,long long temp,int start)
{
    if(step+n-start<k)return;
    if(step==k+1)
    {
        cout << step << ' ' << temp << endl;
        res = max(temp,res);
        return;
    }
    for(int i=start;i<=n;i++)
    {
        dfs(step+1,temp*a[i],i+1);
    }
}




int main()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)cin >> a[i];
    dfs(1,1,1);
    cout << res%MOD << endl;
    return 0;
}

引用一下别人的题解

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long LL;
const int N = 1e5+10;
const int MOD = 1000000009;
LL a[N];
int n,k;
LL res=1;

int main()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)cin >> a[i];
    sort(a+1,a+n+1);
    int l = 1 , r = n;//左右指针
    int sign=1;//符号
    if(k%2) //选奇数个
    {
        res = a[r];
        r--;
        k--;
        if(res < 0)sign = -1; // a1~an全为负数
    }
    while(k)
    {
        LL x = (LL)a[l]*a[l+1], y = (LL)a[r]*a[r-1];
        if(x * sign > y* sign)
        {
            res = x  % MOD * res % MOD; //只能是x %MOD * res % MOD,改变顺序会爆longlong
            l+=2;
        }
        else
        {
            res = y % MOD *  res % MOD;
            r-=2;
        }
        k-=2;
    }
    cout << res <<endl;
    
    return 0;
}