2018省試合第9回ブルーブリッジ杯真題C言語B組第10題題題解積最大

2018第9回ブルーブリッジカップC++省試合B組[最新問題解まとめ]
見出し:積最大
N個の整数A 1,A 2,...AN.その中からK個の数を選んで、その積を最大にしてください. 
最大の積を求めてください.積が整数範囲を超えている可能性があるので、積を1000000009で割った残高を出力するだけです. 
なお、X<0の場合、Xを1000000009で割った剰余は、負(-X)を1000000009で割った剰余であると定義する.
すなわち、0-((0-x)%1000000009)
【入力形式】
第1行は2つの整数NとKを含む. 
以下のN行は行ごとに1つの整数Aiである. 
40%のデータに対して1<=K<=N<=100
60%のデータに対して1<=K<=1000
100%のデータに対して、1<=K<=N<=100000-10000<=Ai<=100000
【出力形式】
答えを表す整数.
【入力サンプル】
5 3 
-100000   
-10000   
2   
100000  
10000  
【出力サンプル】
999100009
次に例を示します.
【入力サンプル】
5 3 
-100000   
-100000   
-2   
-100000  
-100000
【出力サンプル】
-999999829
生産資源約定:
ピークメモリ消費量(仮想マシンを含む)<256 M
CPU消費<1000 ms
考え方:この問題は欲張りで状況を分けることができると思います:まず絶対値によって大きいから小さいまで並べ替えます
①選択したk個の数に必ず0がある場合、結果は0
②いずれも負数である場合、このときkが偶数であれば前のk個の数を選択すればよいが、kが奇数であれば小さいときからk個の数しか選択できない
③いずれも正数であれば、前のk個を選択すればよい
④正負ともにある場合、その場合、前k個の数に偶数個の負数があれば、前k個の数を選択すればよい
前のk個の数に奇数個の負数がある場合、後ろから大きい正数を選んで前の小さい負数と交換できるかどうか、あるいは後ろから大きい負数を選んで前の小さい正数と交換できるかどうかを見て、両者は結果が大きい.
このとき、すべての状況を分ける結果が負数であれば、入力が0であるかどうか、ゼロの結果が0であるかどうかを見てみましょう.そうしないと、この負数しか出力できません.
コード:

#include
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000009
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
const double esp = 1e-7;
const int ff = 0x3f3f3f3f;
map::iterator it;

struct node
{
	ll x;
	int f;
}a[maxn];

int n,k;

bool cmp(node x,node y)
{
	return x.x> y.x;
}

ll solve(int o)
{
	ll ans = 1;
	int cnt = 0;
	if(o == 0)//      
	{
		for(int i = 1;i<= k;i++)
		{
			ans = (ans*a[i].x)%mod;
			if(a[i].f == 1)
				cnt++;
		}
	}
	else//      
	{
		for(int i = n;i> n-k;i--)
		{
			ans = (ans*a[i].x)%mod;
			if(a[i].f == 1)
				cnt++;
		}
	}
	
	if(cnt&1)
		return ans*(-1);
	return ans;
}

int main()
{
	cin>>n>>k;
	
	int flag = 0;
	int cnt = 0;
	for(int i = 1;i<= n;i++)
	{
		scanf("%lld",&a[i].x);
		if(a[i].x< 0)
		{
			a[i].f = 1;
			a[i].x = -a[i].x;
			cnt++;
		}
		else if(a[i].x> 0)
			a[i].f = 0;
		else
		{
			i--;n--;//     0，0          
			flag = 1;
		}
	}
	
	sort(a+1,a+n+1,cmp);
	
	ll ans = 0;
	
	if(n< k)//     0 
		ans = 0;
	else if(cnt == n)//       
	{
		if(k&1)
			ans = solve(1);
		else
			ans = solve(0);
	}
	else if(cnt == 0)//       
		ans = solve(0);
	else
	{
		int tmp = 0;
		for(int i = 1;i<= k;i++)
			if(a[i].f == 1)
				tmp++;
			
		if(tmp%2 == 0)//   k          
			ans = solve(0);
		else
		{
			ans = -1;//        
			//    k                      
			int p = -1,q = -1;
			for(int i = k+1;i<= n;i++)
				if(a[i].f == 0)
				{
					q = i;
					break;
				}
			for(int i = k;i>= 1;i--)
				if(a[i].f == 1)
				{
					p = i;
					break;
				}
			
			if(p!= -1&&q!= -1)
			{
				swap(a[p],a[q]);
				ans = solve(0);
				swap(a[p],a[q]);
			}
			
			//    k                     
			p = -1,q = -1;
			for(int i = k+1;i<= n;i++)
				if(a[i].f == 1)
				{
					q = i;
					break;
				}
			for(int i = k;i>= 1;i--)
				if(a[i].f == 0)
				{
					p = i;
					break;
				}
			
			if(p!= -1&&q!= -1)
			{
				swap(a[p],a[q]);
				ans = max(ans,solve(0));
				swap(a[p],a[q]);
			}
			
			//        0，              
			if(ans< 0)
				ans = solve(1); 
		}
	}
	
	if(ans< 0)
		if(flag)//   0      
		{
			cout<<0<