首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2018-2019 ICPC, NEERC, Northern Eurasia Finals L. Lazyland(思维)

2018-2019 ICPC, NEERC, Northern Eurasia Finals L. Lazyland(思维)

作者头像
Ch_Zaqdt
发布2019-01-10 16:03:27
7060
发布2019-01-10 16:03:27
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

题目链接:http://codeforces.com/contest/1089/problem/L

       题意是有n个人,m份工作,每份工作的编号是1-m,然后输入n个ai,第二行输入n个bi,ai代表当前第i个人所选的工作编号,bi代表如果让这个人去换一个工作所需要花费的权值,现在要让每一份工作都有人去做,问最少需要花费多少可以实现。

       思路就是在输入的时候把每个工作的人数记录下来然后记录一下有多少个工作没有人做,然后对这n个人按照权值从小到大排个序,遍历排序后的每个人,如果这个人选的工作有多个人选了,就让他去选别的工作就行了。


AC代码:

#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
struct Node{
  int id;
  ll w;
  bool operator < (const Node &a) const{
    return a.w > w;
  }
}Edge[maxn];
map<int,int> ma;
int n,m;

int main()
{
  scanf("%d%d",&n,&m);
  int ans = 0;
  for(int i=1;i<=n;i++){
    scanf("%d",&Edge[i].id);
    if(ma[Edge[i].id] == 0) ans ++;
    ma[Edge[i].id] ++;
  }
  for(int i=1;i<=n;i++){
    scanf("%lld",&Edge[i].w);
  }
  ans = m - ans;
  ll sum = 0;
  sort(Edge + 1, Edge + 1 + n);
  for(int i=1;i<=n && ans!=0;i++){
    if(ma[Edge[i].id] > 1){
      ma[Edge[i].id] --;
      sum += Edge[i].w;
      ans--;
    }
  }
  printf("%lld\n",sum);
  return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年12月02日,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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