HDU计算机学院大学生程序设计竞赛（2015’12）1003 The collector’s puzzle-白红宇

HDU计算机学院大学生程序设计竞赛（2015’12）1003 The collector’s puzzle

阅读量：6681 次

发布时间：2019-06-25

本文共 866 字，大约阅读时间需要 2 分钟。

题意：

有N个珠宝 M个箱子珠宝价值a 箱子价值b

每个珠宝放在箱子里，花费abs(a-b)

箱子可以无限放珠宝

求最小花费

水题

预处理每个价值的珠宝所放的箱子O(n)

从左往右找到最接近的左箱子l 从右往左找到最接近的右箱子r

取min

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;const int N=20005;int n,k,m;int l[N],r[N];int v[10*N],s[N];int main(){ int i,j; int T; while(scanf("%d%d",&n,&m)!=EOF) { memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(v,0,sizeof(v)); memset(s,0,sizeof(s)); for(i=1;i<=n;i++) { scanf("%d",&v[i]); } while(m--) { scanf("%d",&i); s[i]=1; } int now=-10000; for(i=1;i<=10000;i++) { if(s[i]) now=i; l[i]=i-now; } now=30000; for(i=10000;i>=1;i--) { if(s[i]) now=i; r[i]=now-i; } long long ans=0; for(i=1;i<=n;i++) { ans+=min(r[v[i]],l[v[i]]); } cout<
           
            <