当前位置:网站首页>Maximum product (greedy)
Maximum product (greedy)
2022-07-06 16:08:00 【AC__ dream】
sample input 1:
5 3
-100000
-10000
2
100000
10000
sample output 1:
999100009
sample input 2:
5 3
-100000
-100000
-2
-100000
-100000
sample output 2:
-999999829
analysis : This is a greedy question , It needs to be discussed according to the situation , We need to store positive and negative numbers separately (0 Treat as positive ), Case one , The number of the given number is the same as the number to be selected , Then it's OK to choose all directly , There is also a situation where all numbers are negative , This should also be discussed separately , Let's sort the negative numbers first , If the number of numbers to be selected is odd , Then the final result must be negative , Then let's start with the largest negative number , choose k Up to the number , Because the larger the negative number, the smaller the absolute value , If the number of numbers to be selected is even , Because the final result is a positive , Then let's start with the smallest negative number , Until you finish selecting .
Now let's focus on how to choose when there are positive numbers , First of all, if you don't select all the numbers ( That is, at least one number can be left blank ) And there are positive numbers , Then the final result must be a non negative number ( At best, we don't choose a positive number or a negative number , This depends on the positive and negative of our product ), At this time, if the number of selected numbers k It's an odd number , Then there is at least one positive number in our final number , So in order to maximize the product , Let's choose the largest positive number first , If k If it is an even number, you don't need to do this step , The rest of us just need to choose an even number , We compare the product of two negative numbers with the largest absolute value and the product of two positive numbers in turn ,( It should be noted that we must choose in pairs ), Who will vote and who will , Until the election is over , This is the optimal solution , The specific code is more complex , Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e5+10,mod=1000000009;
typedef long long ll;
ll z[N],f[N];
int main()
{
int n,k;
int zcnt=0,fcnt=0;
cin>>n>>k;
ll t;
for(int i=1;i<=n;i++)
{
scanf("%lld",&t);
if(t>=0) z[++zcnt]=t;// contain 0
else f[++fcnt]=t;
}
sort(z+1,z+zcnt+1);
sort(f+1,f+fcnt+1);
ll ans=1;
if(fcnt+zcnt==k)
{
for(int i=1;i<=fcnt;i++)
ans=ans*z[i]%mod;
for(int i=1;i<=zcnt;i++)
ans=ans*z[i]%mod;
if(fcnt&1&&ans) printf("-");
printf("%lld",(ans+mod)%mod);
return 0;
}
if(zcnt==0)// There are only negative numbers
{
if(k&1)// The number of selected numbers is odd , Then choose the larger of the negative numbers
{
printf("-");
for(int i=fcnt;i>fcnt-k;i--)
ans=ans*(-f[i])%mod;
}
else// The number of selected numbers is even , Then choose the smaller of the negative numbers
{
for(int i=1;i<=k;i++)
ans=ans*f[i]%mod;
}
}
else// There are positive numbers
{
if(k&1)// The number of selected numbers is odd , First, select the number with the largest median of a positive number , Then compare and select other numbers
ans=ans*z[zcnt--]%mod,k--;
int i,j;
for(i=1,j=zcnt;i<=fcnt&&j>0&&k;)
{
if(f[i]*f[i+1]>z[j]*z[j-1])// Choose two currently selectable minimum negative numbers
{
ans=f[i]*f[i+1]%mod*ans%mod;
i+=2;
k-=2;
}
else// Choose two currently selectable maximum positive numbers
{
ans=z[j]*z[j-1]%mod*ans%mod;
j-=2;
k-=2;
}
}
while(i<=fcnt&&k)
{
ans=f[i]*f[i+1]%mod*ans%mod;
i+=2;
k-=2;
}
while(j>0&&k)
{
ans=z[j]*z[j-1]%mod*ans%mod;
j-=2;
k-=2;
}
}
printf("%lld",(ans+mod)%mod);
return 0;
}
边栏推荐
- JS call camera
- Research Report on market supply and demand and strategy of China's earth drilling industry
- Penetration test (7) -- vulnerability scanning tool Nessus
- 【练习-1】(Uva 673) Parentheses Balance/平衡的括号 (栈stack)
- China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
- Nodejs crawler
- Opencv learning log 15 count the number of solder joints and output
- Frida hook so layer, protobuf data analysis
- Ball Dropping
- CEP used by Flink
猜你喜欢
Programmers, what are your skills in code writing?
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
滲透測試 ( 1 ) --- 必備 工具、導航
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
树莓派4B安装opencv3.4.0
Borg Maze (BFS+最小生成树)(解题报告)
Information security - Analysis of security orchestration automation and response (soar) technology
Quick to typescript Guide
Matlab comprehensive exercise: application in signal and system
Vs2019 initial use
随机推荐
MySQL grants the user the operation permission of the specified content
Interesting drink
Openwrt source code generation image
Opencv learning log 33 Gaussian mean filtering
Opencv learning log 30 -- histogram equalization
605. Planting flowers
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
1689. Ten - the minimum number of binary numbers
Truck History
921. Minimum additions to make parentheses valid
Vs2019 initial use
渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
JS call camera
Penetration test (4) -- detailed explanation of meterpreter command
Ball Dropping
Nodejs crawler
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
The most complete programming language online API document
Opencv learning log 24 -- Hough transform 2 (maximum interval and minimum length can be limited)