Description

Input

Output

Sample Input

輸入樣例1：

3 2 7
5 4 2

輸入樣例2：

5 3 1
5 4 3 5 5

Sample Output

輸出樣例1：

999999732

輸出樣例2：

0

Data Constraint

Solution

• 顯然，乘積最好是負(fù)數(shù)，這樣會(huì)更優(yōu)，那么用一個(gè)布爾型變量 Pd 表示當(dāng)前的負(fù)數(shù)數(shù)量的奇偶性。

• 因?yàn)榧訙p操作的對(duì)象的值的絕對(duì)值一定是當(dāng)前最小的，這樣才會(huì)顯得更優(yōu)（貪心）。

• 于是我們維護(hù)一個(gè)堆，取出其絕對(duì)值最小的那個(gè)，再對(duì) Pd 分類討論：

• 若負(fù)數(shù)數(shù)量為奇數(shù)，說(shuō)明乘積為負(fù)數(shù)；

• 若負(fù)數(shù)數(shù)量為偶數(shù)，說(shuō)明乘積為正數(shù)；

• 再根據(jù)當(dāng)前值的正負(fù)性來(lái)判斷加減，之后壓回堆中即可，時(shí)間復(fù)雜度 O(K?log?N) 。

Code

#include<cstdio> #include<cmath> #include<queue> using namespace std; typedef long long LL; const int N=2e5+1,mo=1e9+7; int n,k,x; int a[N]; bool pd; struct data {int id;data(int x){id=x;}friend bool operator <(data x,data y){return abs(a[x.id])>abs(a[y.id]);} }; priority_queue<data>q; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } int main() {n=read(),k=read(),x=read();for(int i=1;i<=n;i++){a[i]=read();if(a[i]<0) pd=!pd;q.push(data(i));}while(k--){int t=q.top().id;q.pop();if(a[t]<0){if(pd) a[t]-=x; else a[t]+=x;if(a[t]>=0) pd=!pd;}else{if(pd) a[t]+=x; else a[t]-=x;if(a[t]<0) pd=!pd;}q.push(t);}LL ans=1;for(int i=1;i<=n;i++) ans=ans*a[i]%mo;printf("%lld",(ans+mo)%mo);return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5274. 数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。