AcWing 1239. Solution to the maximum product problem using two pointers greedy

topic



Ideas

Here we can discuss on a case-by-case basis:

serial numberConditionHow to takefinal value case
1. k = = n k==n k==nTake all n n numbersDepends on the original sequence
2.k < n k<n k<n and k is evenIf there is an even number of negative numbers, then when we take them, we have to take them in pairs, and we cannot take an odd number of negative numbers; if there are an odd number of negative numbers, then we only need to take the negative numbers in pairs.The result must be non-negative
3.k < n k<n k<n and k is oddIf all numbers are negative, then taking the product of an odd number of negative numbers will always be a negative number; if there is at least one non-negative number, then we can take this non-negative number first, and then add n − 1 n-1 n−1 numbers Select k − 1 k-1 k−1 numbers. The problem returns to the second case, and the result must be non-negative.In the first case the result is negative, in the second case the result must be non-negative

The method can finally be summarized as a greedy + double pointer algorithm:

  1. Sort the sequence from small to large, so there are three possible arrangements: 1) In the sequenceThere are positive numbers and negative numbers: Numbers with large absolute values ​​are at both ends, the left end is a negative number with a large absolute value, the right end is a positive number with a large absolute value, and the number with a small absolute value is in the middle 2) sequenceAll positive numbers: The one with the largest absolute value is on the right end, the one with the smallest absolute value is on the left end 3) In the sequenceAll negative numbers: The larger absolute value is on the left end, and the smaller absolute value is on the right end.
  2. If k k k is an odd number, then take the rightmost number first. It may be the largest positive number, or it may be the negative number with the smallest absolute value (corresponding to the case where all numbers are negative) (But no matter what the situation is, this selection can ensure that the final result is the largest. If there is at least one positive number in the sequence, the final result is a positive number, and you want the absolute value of the result to be the largest, then it will select the largest number from the beginning. taken; if the sequence is all negative numbers and the final result is a negative number, and you want the absolute value of the result to be the smallest, then it starts with the negative number with the smallest absolute value, which also ensures that the absolute value of the final negative number is the smallest, that is, the negative number maximum value), then the problem is transformed into choosing k − 1 k-1 k−1 numbers among n − 1 n-1 n−1 numbers, because k − 1 k-1 k−1 is an even number, then the problem is transformed into the situation 1 1 1
  3. If k k k is an even number, then it belongs to case 1 1 1. You only need to take the larger number pair at both ends of the sorted sequence.

The implementation idea of ​​the algorithm isgreedy, the implementation method isdouble pointer

Details:
It says in the title

In C++, the result of taking modulo a negative number is a negative number, such as − 8 % 5 = − 3 -8\%5=-3 −8%5=−3. The question also explains the inherent properties of C++. Therefore no special treatment is required.


code

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,mod=1000000009;
typedef long long LL;
int a[N];
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n); //Sort
    
    int res=1,sign=1; //res answer, sign marks whether the final result is a negative number or a positive number. If it is a negative number, the number with a smaller absolute value should be taken in the strategy of taking numbers in pairs. If it is a positive number, it should be taken in pairs. In the number strategy, the number with the largest absolute value should be chosen
    int l=0,r=n-1;
    if(k%2) //If k is an odd number
    {
        res=a[r--]; //Take the rightmost number first
        k--;
        if(res<0) sign=-1; // Update the symbol marker for the final answer
    }
    while(k)
    {
        LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1]; //The multiplication of two numbers may be very large, remember to define it as LL
        if(x*sign>y*sign) //Control whether to judge whether the absolute value is large or small
        {
            res=x%mod*res%mod; //Here, x should be modulo first, then multiplied by res, and then modulo the final answer. Don't add brackets blindly, as it is easy to make mistakes. If the operation step here is x%mod multiplied by res%mod, that would be wrong. It may cause the intermediate result to explode, and in the end, you forget to take the modulo of the answer.
            l+=2;
        }
        else
        {
            res=y%mod*res%mod;
            r-=2;
        }
        k-=2; //Because it is taken in pairs, remember to subtract 2 from k
    }
    printf("%d",res);
    return 0;
}

Related Posts

LeetCode 45. Jumping Game ② (Super detailed)

Gas station – detailed explanation of the problem (violence – overall – greedy)

Lanqiao Cup practice system – complete summary of answers to 34 questions in basic exercises (c/c++)

Greedy Algorithm – Merging Fruit Heap Problem (C language analysis has clear ideas)

IPO (Python)

Luogu P1223 queues up to receive water

Related algorithms—greedy algorithm

LeetCode——122. The best time to buy and sell stocks II (dynamic programming, greedy)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*