NC24153. [USACO 2016 Dec P]Robotic Cow Herd
描述
输入描述
The first line of input contains N and K separated by a space.
The following N lines contain a description of the different microcontroller models available for each location. The ith such line starts with Mi (1≤Mi≤10), giving the number of models available for location i. This is followed by Mi space separated integers Pi,j giving the costs of these different models (1≤Pi,j≤100,000,000).
输出描述
Output a single line, giving the minimum cost to construct K robots.
示例1
输入:
3 10 4 1 5 3 10 3 2 3 3 5 1 3 4 6 6
输出:
61
C++(clang++11) 解法, 执行用时: 179ms, 内存消耗: 15580K, 提交时间: 2021-06-30 20:12:49
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=1e5+5;
struct node{
LL sum;int x,y;
bool friend operator<(node a,node b){return a.sum>b.sum;}
};
int n,k,c,id[N],val[N];LL res,ans;
priority_queue<node>q;
vector<int>vec[N];
bool cmp(int x,int y){return val[x]<val[y];}
int main(){
scanf("%d%d",&n,&k);
for(int i=1,x,y;i<=n;i++){
scanf("%d",&x);
if(x==1){scanf("%d",&y);res+=y;continue;}
c++;id[c]=c;
for(int j=1;j<=x;j++)scanf("%d",&y),vec[c].pb(y);
sort(vec[c].begin(),vec[c].end());
res+=(LL)vec[c][0];val[c]=vec[c][1]-vec[c][0];
}
ans=res;k--;n=c;
sort(id+1,id+n+1,cmp);
q.push((node){res+val[id[1]],1,1});
for(int i=1;i<=k;i++){
node u=q.top();q.pop();ans+=u.sum;
if(u.y<vec[id[u.x]].size()-1)q.push((node){u.sum-vec[id[u.x]][u.y]+vec[id[u.x]][u.y+1],u.x,u.y+1});
if(u.x<n)q.push((node){u.sum+val[id[u.x+1]],u.x+1,1});
if(u.x<n&&u.y==1)q.push((node){u.sum-val[id[u.x]]+val[id[u.x+1]],u.x+1,1});
}
printf("%lld\n",ans);
return 0;
}