AtCoder Beginner Contest 173 E Multiplication 4 分类讨论贪心

LINK：Multiplication 4

害怕别人不知道我有多菜那就上张图:

赛时太慌了 (急着AK

题目不难却暴露我的本性根本不思考无脑写 wa了还一直停不下来的debug 至少被我发现了10个漏洞且最后还存在bug.

放弃治疗然后走人了。啊啊啊下次再不认真思考我把番给戒了.

原本的想法是有负数的时候很难办先把0分开然后负数两两组合正数也是如此然后开始贪心。

最后特判k为1的情况这个情况接一堆分类讨论但是当时少讨论一种情况代码过于繁杂导致GG.

今天花了几分钟想了一种比较简单的做法：每个数字取绝对值直接从大到小选数字。

分类讨论最后得到的数字是否是负值正值显然ok 为0也特判掉。

那么如果为负值想办法替换成正值无非是去掉一个正值加上一个负值去掉一个负值加上一个正值两种情况。两种情况比max即可。

证明这样是最优的：显然前k-2个数字是最大的且为正数这是最优的最后两个数字要么放两个正数其中第一种情况是这个地方的最优放两个负数这两个也同样最优。

所以这样做一下就行了比较好写细节不多。

code

//#include<bits\stdc++.h>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 10000000000000010ll

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define gc(a) scanf("%s",a+1)

#define rep(p,n,i) for(RE ll i=p;i<=n;++i)

#define go(x) for(ll i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE ll i=n;i>=p;--i)

#define vep(p,n,i) for(RE ll i=p;i<n;++i)

#define pii pair<ll,ll>

#define mk make_pair

#define RE register

#define P 1000000007

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-8

#define sq sqrt

#define S second

#define F first

#define mod 1000000007

using namespace std;

char buf[1<<15],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline ll read()

{

    RE ll x=0,f=1;RE char ch=getc();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}

    return x*f;

}

const ll MAXN=200010;

ll n,k,cnt1,cnt2,ww;

ll a[MAXN],b[MAXN],vis[MAXN],c[MAXN];

priority_queue<pii>q;

inline ll cmp(ll x,ll y){return x>y;}

inline ll ksm(ll b,ll p)

{

	ll cnt=1;

	while(p)

	{

		if(p&1)cnt=(ll)cnt*b%mod;

		b=(ll)b*b%mod;p=p>>1;

	}

	return cnt;

}

signed main()

{

	freopen("1.in","r",stdin);

	get(n);ww=get(k);ll mark=0;

	rep(1,n,i)

	{

		get(c[i]);

		if(c[i])q.push(mk(abs(c[i]),c[i]>0));

		else ++mark;

	}

	if(q.size()<k)puts("0");

	else

	{

		ll ans=1,cnt=1,w1=0,w2=0;

		while(q.size()&&k)

		{

			pii w=q.top();q.pop();

			if(!w.S)cnt=cnt^1,w2=w.F;

			else w1=w.F;

			ans=ans*w.F%mod;

			--k;

		}

		if(cnt)putl(ans);

		else

		{

			ll c1=0,c2=0;

			while(q.size())

			{

				pii w=q.top();q.pop();

				if(!c1&&w.S>0)c1=w.F;

				if(!c2&&!w.S)c2=w.F;

			}

			if((!c2||!w1)&&(!c1||!w2))

			{

				if(mark)puts("0");

				else

				{

					rep(1,n,i)c[i]=abs(c[i]);

					sort(c+1,c+1+n);ans=1;

					rep(1,ww,i)ans=ans*c[i]%mod;

					ans=mod-ans;putl(ans);return 0;

				}

			}

			else

			{

				if(!c1||!w2)

				{

					ans=ans*ksm(w1,mod-2)%mod;

					ans=ans*c2%mod;putl(ans);

					return 0;

				}

				if(!c2||!w1)

				{

					ans=ans*ksm(w2,mod-2)%mod;

					ans=ans*c1%mod;putl(ans);

					return 0;

				}

				if(w1*c1>w2*c2)

				{

					ans=ans*ksm(w2,mod-2)%mod;

					ans=ans*c1%mod;putl(ans);

					return 0;

				}

				else

				{

					ans=ans*ksm(w1,mod-2)%mod;

					ans=ans*c2%mod;putl(ans);

					return 0;

				}

			}

		}

	}

	return 0;

}

巴特西

AtCoder Beginner Contest 173 E Multiplication 4 分类讨论贪心

最新文章

热门文章

巴特西

AtCoder Beginner Contest 173 E Multiplication 4 分类讨论 贪心

最新文章

热门文章

AtCoder Beginner Contest 173 E Multiplication 4 分类讨论贪心