首页 > 代码库 > CodeForces 721D Maxim and Array

CodeForces 721D Maxim and Array

2024-08-15 09:43:36   217人阅读

　　题意：给出n个数，k次机会，每次机会可以使得任意一个数字减少或者加上x，问使得最后的乘积最小的n个数，每个数是多少。

　　分析：贪心思路是每次取出绝对值最小的一个数，判断乘积的符号以及这个数的符号来做出加或者减的操作。

　　具体见代码：

 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 #include <queue> 6 #include <math.h> 7 using namespace std; 8  9 const int N = 200000 + 50;10 typedef long long ll;11 12 ll aabs(ll x) {return x<0 ? -x : x;}13 14 struct node15 {16     ll num;17     int id;18     bool operator < (const node & temp) const19     {20         return aabs(num) > aabs(temp.num);21     }22 };23 24 ll a[N];25 ll n,k,x;26 27 int main()28 {29     cin >> n >> k >> x;30     int sign = 1;31     priority_queue<node> Q;32     for(int i=1;i<=n;i++)33     {34         scanf("%I64d",a+i);35         if(a[i] < 0) sign = -sign;36         Q.push((node){a[i],i});37     }38     while(k--)39     {40         node temp = Q.top();Q.pop();41         if(a[temp.id] < 0)42         {43             if(sign == -1) a[temp.id] -= x;44             else a[temp.id] += x;45             if(a[temp.id] >= 0) sign = -sign;46         }47         else48         {49             if(sign == -1) a[temp.id] += x;50             else a[temp.id] -= x;51             if(a[temp.id] < 0) sign = -sign;52         }53         Q.push((node){a[temp.id],temp.id});54     }55     for(int i=1;i<=n;i++)56     {57         printf("%I64d%c",a[i],i==n?‘\n‘:‘ ‘);58     }59 }

 

　　顺便回顾一下，优先队列是默认的每次弹出优先级最大的元素（默认less），，好久没用优先队列都忘了= =。。

CodeForces 721D Maxim and Array


联系
我们