Codeforces Round #374 (Div. 2) D. Maxim and Array-白红宇

Codeforces Round #374 (Div. 2) D. Maxim and Array

阅读量：6693 次

发布时间：2019-06-25

本文共 3808 字，大约阅读时间需要 12 分钟。

分析：其实没什么好分析的。统计一下负数个数。如果负数个数是偶数的话，就要尽量增加负数或者减少负数。是奇数的话就努力增大每个数的绝对值。用一个优先队列搞一下就行了。我感觉这道题的细节极为多，非常复杂，其实是自己智障了。。

我看了一下学长菊苣的代码，好精巧。。。注释部分是他的代码

/*****************************************************///#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define offcin ios::sync_with_stdio(false)#define sigma_size 26#define lson l,m,v<<1#define rson m+1,r,v<<1|1#define slch v<<1#define srch v<<1|1#define sgetmid int m = (l+r)>>1#define LL long long#define ull unsigned long long#define mem(x,v) memset(x,v,sizeof(x))#define lowbit(x) (x&-x)#define bits(a) __builtin_popcount(a)#define mk make_pair#define pb push_back#define fi first#define se secondconst int INF = 0x3f3f3f3f;const LL INFF = 1e18;const double pi = acos(-1.0);const double inf = 1e18;const double eps = 1e-9;const LL mod = 1e9+7;const int maxmat = 10;const ull BASE = 31;/*****************************************************/const int maxn = 2e5 + 5;struct Node { LL pos, val;}node[maxn];struct kk { LL pos, val; bool operator <(const kk &rhs) const { return abs(val) > abs(rhs.val); }};priority_queue
                    
                      q;int N, k, x;bool cmp1(const Node &a, const Node &b) { return a.val < b.val; }bool cmp2(const Node &a, const Node &b) { return a.pos < b.pos; }int main(int argc, char const *argv[]) { cin>>N>>k>>x; int neg = 0; int flag = 1; for (int i = 0; i < N; i ++) { cin>>node[i].val; node[i].pos = i; if (node[i].val < 0) neg ++; } sort(node, node + N, cmp1); if (neg && (neg & 1) == 0) { int lb = 0, ub = N - 1, res = -1; while (lb <= ub) { int mid = (lb + ub) >> 1; if (node[mid].val < 0) { res = mid; lb = mid + 1; } else ub = mid - 1; } bool flag1 = false, flag2 = false; if ((LL)k * x + node[res].val >= 0) flag1 = true; if ((LL)-k * x + node[res + 1].val < 0) flag2 = true; if (res == N - 1) { if ((LL)k * x + node[res].val >= 0) { LL temp1 = ((-node[res].val - 1) / x + 1); k -= temp1; node[res].val += temp1 * x; } else flag = -1; } else if (flag1 && flag2) { LL temp1 = ((-node[res].val - 1) / x + 1); LL temp2 = (node[res + 1].val / x + 1); // cout<
                     
                      <<" "<
                      
                       <
                       
                         abs(node[res + 1].val)) { k -= temp2; node[res + 1].val -= temp2 * x; } else { k -= temp1; node[res].val += temp1 * x; } } else if (temp1 > temp2) { k -= temp2; node[res + 1].val -= temp2 * x; } else { k -= temp1; node[res].val += temp1 * x; } } else if (flag1) { int temp1 = ((-node[res].val - 1) / x + 1); k -= temp1; node[res].val += temp1 * x; } else if (flag2) { int temp2 = (node[res + 1].val / x + 1); k -= temp2; node[res + 1].val -= temp2 * x; } else flag = -1; } else if (neg == 0) { if ((LL)-x * k + node[0].val < 0) { LL temp = (node[0].val / x + 1); k -= temp; node[0].val -= temp * x; } else flag = -1; } for (int i = 0; i < N; i ++) q.push((kk){node[i].pos, node[i].val}); while (k > 0) { kk temp = q.top(); q.pop(); if (temp.val < 0) temp.val -= flag * x; else temp.val += flag * x; k --; q.push((kk){temp.pos, temp.val}); } int p = 0; while (!q.empty()) { kk temp = q.top(); q.pop(); node[p ++] = (Node){temp.pos, temp.val}; } sort(node, node + N, cmp2); for (int i = 0; i < N; i ++) cout<
                        
                         <<" "; return 0;}// LL a[MAX];// struct Edge{ // LL a,b;// int id;// bool operator < (const Edge &e)const{ // return a>e.a;// }// };// LL labs(LL a){ // if(a<0) return -a;// return a;// }// int main(){ // //freopen("in.txt","r",stdin);// int n,k,x;// while(cin>>n>>k>>x){ // int fu=0;// priority_queue
                         
                           q;// for(int i=0;i
                          
                           =0) fu--;// }// else{ // tmp.b-=x;// if(tmp.b<0) fu++;// }// tmp.a=labs(tmp.b);// a[tmp.id]=tmp.b;// }// q.push(tmp);// }// for(int i=0;i

转载于:https://www.cnblogs.com/hahatianx/p/5943437.html

你可能感兴趣的文章