[Solution] CF767E Change-free

Los Valley Links

Forgot to enter the translation of this question, I read the English original...

First, it's a greedy problem

Greedy strategy:

From the first day to the last day, you can choose to ask for money or not to ask for money every day. If you do not ask for money, the amount of change m minus the extra change; .

In this case, we can use our greedy thinking. If the amount of change in hand is sufficient, we can choose to pay the change we need with the change in our hand; Looking back in time, on that day I chose to pay 100 yuan for change and let the uncle find the money, so you have an extra 100 yuan in change, but the uncle is even more angry...

 

Which day do you choose?

Still thinking about it? Of course, it was the day when the increase in Uncle's anger was the smallest.

I thought of this, crackling through the code and committing with confidence

result:

 

I:? ? ? ? ? ?

I:! ! ! ! ! !

Well, it seems to be optimized

I pondered hard (I didn't read the solution this time), and thought that since it is seeking the dynamic maximum value, it would be better to use heap optimization~

So I hit a heap excellent, and the second example couldn't pass.

I changed it over and over again, and finally the samples are all over~

Submitted it, and I saw a green ~~

Note: Remember to open long long

AC code:

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 100001
#define LL long long
#define M(i, j) make_pair(i, j)
using namespace std;

LL c[MAXN], w[MAXN], zheng[MAXN], ling[MAXN];//zheng[i] is the number of 100 yuan spent on the i-th day, and ling[i] is the amount of change spent on the i-th day
LL n, m, h, k, ans=0;
int vis[MAXN];
priority_queue<pair<LL, LL>, vector< pair<LL, LL> >, greater< pair<LL, LL> > > q;//Small Head Pile (Hooray STL!)

int main(){

  scanf("%lld %lld", &n, &m);
  for (int i = 1; i <= n; i++){
  scanf("%lld", &c[i]);
  zheng[i] = c[i] / 100;//Figure out how much you spend at least $100 a day
  c[i] %= 100;//Preprocessing, c[i] only needs to spend change
  }
  for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
  for (int i = 1; i <= n; i++){
    ling[i] += c[i];//It is not allowed to give more money in the question. If you just pay the 100 yuan, you will not be able to exchange it for change.
    if (c[i]) q.push(M(w[i]*(100 - c[i]), i));//Use the pair type to store the number of days and the anger value that the uncle may rise in the heap (the pair type is sorted by first by default)
    if (c[i] > m){
      h = q.top().first;//Take out the minimum rage
      k = q.top().second;//What day is it taken out
      q.pop();
      vis[k] = 1;//Mark the day that the change has been changed (this sentence seems useless)
      ans += h;//build up rage
      ling[k] -= c[k];//No change for that day
      zheng[k]++;//100 yuan integer +1 on that day
      m += 100;//Extra 100 yuan in change
    }
    m -= c[i];
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++){
    printf("%lld %lld\n", zheng[i], ling[i]);
  }
  return 0;
}

 

Hope to help you~~⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄.

 

Tags: greedy algorithm

Posted by Adarmo on Fri, 13 May 2022 19:50:54 +0300