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

本文主要是介绍2018-2019 ICPC, NEERC, Northern Eurasia Finals L- Lazyland(思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define ll long long
struct People
{int xz,time;
}a[maxn];
int c[maxn];
bool cmp(People a, People b)
{return a.time < b.time;
}
int main()
{int n, k; scanf("%d%d",&n,&k);for(int i = 1; i <= n; i++){scanf("%d",&a[i].xz);c[a[i].xz]++;}for(int i = 1; i <= n; i++) scanf("%d",&a[i].time);sort(a+1,a+1+n,cmp); int cnt = 0; ll ans = 0;for(int i = 1; i <= k; i++)if(!c[i]) cnt++;for(int i = 1; i <= n && cnt; i++){if(c[a[i].xz] > 1){c[a[i].xz]--;ans += a[i].time,cnt--;}}printf("%lld\n",ans);
}

vector写法：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,a[100005],b[100005],cnt;
vector < int > vec[100005],can;
int main()
{scanf("%d%d",&n,&m);for(int i = 0; i < n; ++i){scanf("%d",a+i);--a[i];}for(int i = 0; i < n; ++i)scanf("%d",b+i);for(int i = 0; i < n; ++i)vec[a[i]].push_back(b[i]);LL res = 0ll;for(int i = 0; i < m; ++i){if(vec[i].empty()) ++cnt;sort(vec[i].begin(),vec[i].end());for(int j = 0; j < (int)vec[i].size()-1; ++j)can.push_back(vec[i][j]);}sort(can.begin(),can.end());for(int i = 0; i < cnt; ++i) res += (LL)can[i];printf("%lld\n",res);return 0;
}

 

这篇关于2018-2019 ICPC, NEERC, Northern Eurasia Finals L- Lazyland(思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---