【题解】 CF767E Change-free

洛谷链接

这个题翻译忘了输入,我看的英语原文......

首先,这是一道贪心题

贪心策略:

从第一天开始,到最后一天,每天可以选择找钱或者不找钱,如果不找钱,则零钱数m减去多出的零钱;如果找钱,则食堂大爷的怒气值上升找钱数乘每天心情值w。

既然这样,我们就可以利用贪心思想,如果手中的零钱数是足够的,就选择用手中的零钱支付所需要的零钱;如果手中的零钱数不够,就找出之前用零钱支付零钱的天,让时间回溯,在那一天选择用100元支付零钱,让大爷找钱,这样你就多出了100元的零钱,只不过大爷更生气了而已......

 

选哪一天呢?

还用想吗?当然是使大爷怒气值上升最小的那一天啊。

我想到这里,噼里啪啦地打完了代码,满怀信心地提交

结果:

【题解】 CF767E Change-free

 

我:??????

我:!!!!!!

好吧,看来得优化

我冥思苦想(这次没看题解),想到既然是求动态最大值,那用堆优不就好啦~

于是我打上去一个堆优,结果样例二又过不去了

我就这样改了一遍又一遍,总算样例都过了~

提交上去,果然看到了一片绿~~

注意:记得开long long

AC代码:

 

#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]是第i天100元花费的个数,ling[i]是第i天零钱花费的元数
LL n, m, h, k, ans=0;
int vis[MAXN];
priority_queue<pair<LL, LL>, vector< pair<LL, LL> >, greater< pair<LL, LL> > > q;//小头堆(STL万岁!)

int main(){

  scanf("%lld %lld", &n, &m);
  for (int i = 1; i <= n; i++){
  scanf("%lld", &c[i]);
  zheng[i] = c[i] / 100;//算出每天至少花费多少100元
  c[i] %= 100;//预处理,c[i]只存需花费零钱
  }
  for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
  for (int i = 1; i <= n; i++){
    ling[i] += c[i];//题目中不允许多给钱,如果用100元正好支付完就无法来换零钱
    if (c[i]) q.push(M(w[i]*(100 - c[i]), i));//用pair类型将天数与大爷可能上升的怒气值存进堆里(pair类型默认用first来排序)
    if (c[i] > m){
      h = q.top().first;//取出最小怒气值
      k = q.top().second;//取出是哪一天
      q.pop();
      vis[k] = 1;//标记这一天已经换了零钱了(这句好像没用)
      ans += h;//积累怒气值
      ling[k] -= c[k];//那一天不用找零了
      zheng[k]++;//那一天100元整数+1
      m += 100;//多出100元零钱
    }
    m -= c[i];
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++){
    printf("%lld %lld\n", zheng[i], ling[i]);
  }
  return 0;
}

 

希望能帮到您~~⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄.

 

上一篇:P7042 「MCOI-03」正方


下一篇:BZOJ-3834 [Poi2014]Solar Panels(数论分块)