首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round #536 (Div. 2) B. Lunar New Year and Food Ordering(思维)

Codeforces Round #536 (Div. 2) B. Lunar New Year and Food Ordering(思维)

作者头像
Ch_Zaqdt
发布2019-03-05 10:35:53
4210
发布2019-03-05 10:35:53
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

题目链接:http://codeforces.com/contest/1106/problem/B

       题意是有n个菜,m个操作,接下来一行输入每个菜的盘数,再下来一行输入每盘菜的价格,接下来m行,每行两个数分别表示第x个菜,要买y盘,输出他要支付的价钱,如果第x个菜不够y盘,他将会去买价格最低的菜,直到买够y盘,如果所有的菜都卖完了也不够y盘,他就会不高兴,然后带着那些不够y盘的菜不给钱就走了。

       比较巧妙的思维题,写法就是按题意分类讨论然后模拟就完了,暴力的去模拟的话,亲测TLE,然后这里需要一个巧妙的转换,就是开一个id数组,将每盘菜的id按它的价格排序,然后用一个变量去记录并更新最便宜的菜的位置就好了。说的不太清楚,看呆码理解吧,不是很难。


AC代码:

#include <bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
int w[maxn], cnt[maxn], id[maxn];
int n,m;

bool cmp(int x,int y){
  return w[x] < w[y];
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    scanf("%d",&cnt[i]);
    id[i] = i;
  }
  for(int i=1;i<=n;i++) scanf("%d",&w[i]);
  sort(id + 1, id + n + 1, cmp);       // 按价格排序
  int pos = 1;         // 标记最便宜的菜的位置
  while(m--){
    int x, y;
    scanf("%d%d",&x,&y);
    int p = min(cnt[x], y);            // 取二者最小值
    ll ans = (ll)p * (ll)w[x];
    cnt[x] -= p; y -= p;
    while(y && pos <= n){              // 如果y有剩余,进入while循环
      if(cnt[id[pos]] == 0) pos++;     // 如果第pos便宜的菜卖完了 pos++
      p = min(cnt[id[pos]] , y);
      ans += (ll)p * (ll)w[id[pos]];
      cnt[id[pos]] -= p;
      y -= p;
    }
    if(y == 0) printf("%lld\n", ans);
    else puts("0");
  }
  return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年02月01日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档