NC54318. Lazyland
描述
输入描述
The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 105) — the number of idlers and the number of jobs.
The second line of the input contains n integers a1, a2, …, an (1 ≤ ai ≤ k) — the jobs chosen by each idler.The third line of the input contains n integers b1, b2, …, bn (1 ≤ bi ≤ 109) — the time the King needs to spend to persuade the i-th idler.
输出描述
The only line of the output should contain one number — the minimum total time the King needs to
spend persuading the idlers to get all the jobs done.
示例1
输入:
8 7 1 1 3 1 5 3 7 1 5 7 4 8 1 3 5 2
输出:
10
说明:
In the first example the optimal plan is to persuade idlers 1, 6, and 8 to do jobs 2, 4, and 6.示例2
输入:
3 3 3 1 2 5 3 4
输出:
0
说明:
In the second example each job was chosen by some idler, so there is no need to persuade anyone.C++11(clang++ 3.9) 解法, 执行用时: 124ms, 内存消耗: 6164K, 提交时间: 2020-10-07 22:13:31
#include<bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll> a[100005];
map<ll,ll>mp;
int main()
{
ll n,k,i;
cin>>n>>k;
for(i=1;i<=n;i++)
{
cin>>a[i].second;
mp[a[i].second]++;
}
for(i=1;i<=n;i++)
{
cin>>a[i].first;
}
sort(a+1,a+n+1);
ll ans=0,f=0;
for(i=1;i<=n;i++)
{
if(f+mp.size()==k)
break;
if(mp[a[i].second]>1)
{
mp[a[i].second]--;
ans+=a[i].first;
f++;
}
}
cout<<ans;
}
C++14(g++5.4) 解法, 执行用时: 128ms, 内存消耗: 5880K, 提交时间: 2020-10-06 14:03:29
#include<bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll> a[100005];
map<ll,ll>mp;
int main()
{
ll n,k,i;
cin>>n>>k;
for(i=1;i<=n;i++)
{
cin>>a[i].second;
mp[a[i].second]++;
}
for(i=1;i<=n;i++)
{
cin>>a[i].first;
}
sort(a+1,a+n+1);
ll ans=0,f=0;
for(i=1;i<=n;i++)
{
if(f+mp.size()==k)
break;
if(mp[a[i].second]>1)
{
mp[a[i].second]--;
ans+=a[i].first;
f++;
}
}
cout<<ans;
}
pypy3(pypy3.6.1) 解法, 执行用时: 166ms, 内存消耗: 38452K, 提交时间: 2020-10-06 12:31:22
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=[]
for i in range(m):
C.append([])
D=[]
c=0
for i in range(n):
C[A[i]-1].append(B[i])
for i in range(m):
if len(C[i])==0:
c+=1
else:
C[i].sort()
for j in range(len(C[i])-1):
D.append(C[i][j])
D.sort()
ans=0
for i in range(c):
ans+=D[i]
print(ans)