题目内容

小 A 有 $n$ 张卡牌，这 $n$ 张卡牌初始时都放在桌子上，第 $i$ 张上写有一个非负整数 $a_i$。

接下来小 A 会选出一些卡牌，第一轮他会从桌子上选出一张上面写有奇数的卡牌拿到手上，第二轮他会选出一张上面写有偶数的卡牌拿到手上，以此类推，轮数为奇数时他需要选一张上面写有奇数的卡牌，轮数为偶数时他需要选一张写有偶数的卡牌。

小 A 可以一直进行选牌操作，直到他一共选出了 $k$ 张牌拿在手上，或者某一轮的时候他没有对应奇偶性的牌可拿了。小 A 想要知道他选出的牌上的数字和最大是多少？

输入格式

第一行两个整数 $n,k$，表示卡牌数量和小 A 最多选几张牌。

第二行 $n$ 个以空格分隔的非负整数 $a_1,a_2,\dots, a_n$。

输出格式

输出一行一个整数表示答案。

【数据范围】

对于 $40\%$ 的数据，$n\le 1000$。

对于另外 $20\%$ 的数据，保证 $n$ 为偶数且 $a_1,a_2,\dots, a_n$ 中偶数和奇数都各有 $\frac{n}{2}$ 个。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le k\le n$，$0\le a_i\le 1000$。

代码

#include <iostream>
#include <algorithm>
using namespace std;
signed main()
{
	int n,k,a[100005],x[100005],y[100005],sum=0,num=0,ans=0,m;
	cin>>n>>k;
	if(n%2==0)
	{
		m=2;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i%2!=0)
		{
			sum++;
			x[i]=a[i];
		}
		else
		{
			num++;
			y[i]=a[i];
		}
	}
	sort(x+1,x+sum+1);
	sort(y+1,y+num+1);
	for(int i=n;i>=n-k+1;i--)
	{
		if(m==1)
		{
			if(x[i]!=0)
			{
				ans+=x[i];
			}
			else
			{
				cout<<ans;
				return 0;
			}
		}
		else
		{
			if(y[i]!=0)
			{
				ans+=y[i];
			}
			else
			{
				cout<<ans;
				return 0;
			}
		}
		if(m==2)
		{
			m--;
		}
		else
		{
			m++;
		}
	}
	return 0;
}