Maxim and Array CodeForces - 721D (贪心)

大意: 给定序列, 每次操作选择一个数+x或-x, 最多k次操作, 求操作后所有元素积的最小值

贪心先选出绝对值最小的调整为负数, 再不断选出绝对值最小的增大它的绝对值

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
//head const int N = 1e6+10;
int n, k, x;
struct _ {
ll w;
int id;
bool operator < (const _ &rhs) const {
return abs(w) > abs(rhs.w);
}
} e[N];
ll ans[N];
int sgn(ll x) {return x<0?-1:1;}
int main() {
scanf("%d%d%d", &n, &k, &x);
int f = 0;
REP(i,1,n) scanf("%lld", &e[i].w), e[i].id=i, f^=e[i].w<0;
if (!f) {
_ *r = max_element(e+1,e+1+n);
if (!r->w) --k,r->w-=x;
else {
int ff = sgn(r->w);
while (k) {
r->w -= sgn(r->w)*x, --k;
if (sgn(r->w)!=ff) break;
}
}
}
priority_queue<_> q;
REP(i,1,n) q.push(e[i]);
while (k) {
_ t = q.top(); q.pop();
t.w += sgn(t.w)*x;
q.push(t), --k;
}
while (q.size()) ans[q.top().id]=q.top().w,q.pop();
REP(i,1,n) printf("%lld ", ans[i]);hr;
}
上一篇:HDU - 3973 AC's String(Hash+线段树)


下一篇:outlook 2003配置连接exchange server 2010报错——无法完成此操作。 与 Microsoft Exchange Server 的连接不可用。 Outlook 必须联机或连接才可完成该操作