题目简述
小 A 想要给他的朋友小 B 发送了一条有 $m$ 个单词的消息。他们的语言由编号从 $a_1$ 到 $a_n$ 的 $n$ 个单词组成。一些单词具有相同的意思,因此存在 $k$ 个单词组,其中每个组中的所有单词具有相同的意思。小A知道第 $i$ 个单词可以以成本 $m_i$ 发送。
对于他的每个消息中的单词,小A可以将其替换为具有相同意思的另一个单词,或者保持不变。请帮助小A确定发送消息的最小价值。
发送消息的成本是其中每个单词的发送成本的总和。
题目分析
对于单词 $s$,我们一定会将 $s$ 换成它所在的组中价值最低的一个,依据此贪心思路模拟即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof a)
const int N=1e5+10;
int n,k,m,vis[N],x,Min[N];
ll ans;
string q;
map<string,int> Vis;
struct word
{
string s;
int val;
}a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k>>m;
mem(Min,0x3f);
For(i,1,n)
{
cin>>a[i].s;
Vis[a[i].s]=i;
}
For(i,1,n)
{
cin>>a[i].val;
}
For(i,1,k)
{
cin>>x;
int temp=0;
while(x--)
{
cin>>temp;
vis[temp]=i;
Min[i]=min(Min[i],a[temp].val);
}
}
For(i,1,m)
{
cin>>q;
ans+=Min[vis[Vis[q]]];
}
cout<<ans;
return 0;
}
标签:temp,Min,int,题解,cin,Codeforces,单词,959B,define
From: https://www.cnblogs.com/zhuluoan/p/18198755