预习功课

我通过这个题接触到了stl中的heap。

以前都是用set啊啥的，然而如果你把n个元素全都插入到set里复杂度是相当的高的。这个时候heap就产生了，而且heap有一个好，它的内部不是有序的，要求没有那么严格，所以这个时候我们就要用heap了。

heap的使用

假设我们定义了一个vector <int> s;

头文件

#include <algorithm>

make_heap

make_heap(s.begin(), s.end());

有时根据自己的需要，可以加入自定义cmp函数。加cmp的写法是：make_heap(s.begin(), s.end(), cmp);未加声明时默认是大根堆。

pop_heap

pop_heap(s.begin(), s.end());

这个函数并不是真的删掉了最大的元素，而是将最大的元素与原来的最后一项交换，再维护前s.size()-1个元素的性质。

push_heap

push_heap(s.begin(), s.end());

跟pop_heap很相似，是将新的元素加在s的末尾之后重新维护堆的性质。

sort_heap

sort_heap(s.begin(), s.end());

就是对这个堆进行排序，排序之后它就不再是一个堆了，而是一个完全有序的容器。

Example Code

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main () {  int myints[] = {10, 20, 30, 5, 15};  vector 
       
         v(myints, myints+5);  make_heap(v.begin(), v.end());  cout << "initial max heap   : " << v.front() << endl;  pop_heap(v.begin(),v.end()); v.pop_back();  cout << "max heap after pop : " << v.front() << endl;  v.push_back(99); push_heap (v.begin(), v.end());  cout << "max heap after push: " << v.front() << endl;  sort_heap (v.begin(), v.end());  cout << "final sorted range :";  for (unsigned i=0; i < v.size(); i++) cout << " " << v[i];  cout << endl;  return 0;}
       
      
     
    

输出结果：

initial max heap   : 30max heap after pop : 20max heap after push: 99final sorted range : 5 10 15 20 99

当然

我们其实不一定要用vector，数组也是可以的，只要函数里的两个位置是开头和结尾的指针就行。

比如我们定义了一个：int a[6] = {3, 5, 2, 1, 4};那么调用make_heap只需make_heap(a, a+5);就行。

进入正题

题意

给你n,k,x以及n个数a₁,a₂,...,a_n每次操作你可以对a_i进行+x或者-x，总共k次，且这些操作需最小化$$prod_{i=1}^{n} a_i$$ 问k次操作之后每个元素各是多少。

想法

首先肯定要分类讨论一下。令$$s = prod_{i=1}^{n} a_i$$如果s是正的，那么我们一定会想减小绝对值最小的那个数的绝对值，最好能让s变负数，如果s本身就是负数，那么我们只需考虑所有数的绝对值，然后让绝对值最小的那个数的绝对值增大（为什么是绝对值最小的而不是最大的你做个商就好了）。每次操作都是对绝对值最小的那个数进行操作，显然这就需要用到堆了。

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ll long long #define db double#define N 200010#define max(a, b) ((a) > (b) ? (a) : (b))#define min(a, b) ((a) < (b) ? (a) : (b))#define swap(T, a, b) ({T ttt = a; a = b; b = ttt;})using namespace std;#define Sig(x) (x < 0 ? -1 : 1)ll a[N], b[N], x; int n, k, sig = 1; bool cmp(int x, int y) { return abs(a[x]) > abs(a[y]); } int main(){   scanf("%d%d%I64d", &n, &k, &x);    for (int i = 1; i <= n; i++)      scanf("%I64d", &a[i]), sig *= Sig(a[i]), b[i] = i;   make_heap(b+1, b+n+1, cmp);    while (k--) {        int t = sig * Sig(a[b[1]]);         a[b[1]] -= t * x;        sig = t * Sig(a[b[1]]);         pop_heap(b+1, b+n+1, cmp);         push_heap(b+1, b+n+1, cmp);     }    for (int i = 1; i <= n; i++)        printf("%I64d ", a[i]);     return 0; }