题意分析

题意是某国得到可能遭受核打击的情报，需要将人群撤离进避难所中，给予n只队伍的位置，以及m个避难所的位置，然后要求每个队伍都要进入避难所中，且每个避难所中至少有一只队伍，求最小的油耗和为多少（油耗为队伍走过的距离）。

解题思路

将这些队伍和避难所的位置都从小到大排好，然后就是决定这些队伍的去向了：1.最简单明了的跑到最近的避难所中。（逃命要紧）2.做点贡献跑远点到一个没人的避难所中（题目要求每个避难所中至少有一只队伍，因为要人把门给关上，防止避难所被炸了）。第一个选择可以说是确定跑哪里去的，主要看第二个选择，如果选择进入一个无人避难所中，那这个避难所应该是最左边那个无人避难所，（我这里是从左到右处理的，反之就是最右边的无人避难所）。对于这个选择只要举个例子验证下就好，如果队伍和避难所的前后关系为：a-A-B-b（大写字母为避难所，小写字母为队伍），从左到右处理，如果a选择避难所B，那么b就只能选择避难所A，而他们走过的路线出现了反向交叉，即A-B这段路多跑了两次，所以我们要防止反向交叉路线出现（同向走没问题），那么就只要让避难所从左到右入户就行了。

那么递推公式就出来了$dp[i] [t] = min { dp [i-1] [t] + best, dp [i-1] [t-1] + Abs(Team [i] - Shelt [t])}$，$dp [i] [t]$代表的是前i只队伍入户了前t个避难所的最优油耗，而其中的best是在前t个避难所中，离队伍i最近的避难所的距离，这个值只要在循环中跟着更新就行。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long LL;  // Using long long instead of int64_t

const int MAXM = 4002;
const int INF = 0x3f3f3f3f;

int Hav;
int Num;
int Ans[MAXM];

struct P
{
    int id;
    int val;
    bool operator < (const P& a)const
    {
        return val < a.val;
    }
}Team[MAXM], Shelt[MAXM];

LL A[MAXM], B[MAXM];

int Map[MAXM][MAXM];

int Abs(int a)
{
    return a > 0 ? a : -a;
}

void Read_Case()
{
    scanf("%d", &Hav);
    for (int i = 1; i <= Hav; i++)
    {
        scanf("%d", &Team[i].val);
        Team[i].id = i;
    }
    scanf("%d", &Num);
    for (int i = 1; i <= Num; i++)
    {
        scanf("%d", &Shelt[i].val);
        Shelt[i].id = i;
    }
    sort(Team + 1, Team + Hav + 1);
    sort(Shelt + 1, Shelt + Num + 1);
}

void Deal()
{
    int best, pos, dis;
    LL inf = (LL)INF * MAXM;
    LL* Ago = A, * Now = B, * G;
    for (int i = 0; i <= Num; i++) Ago[i] = inf;
    Ago[0] = 0;
    
    for (int i = 1; i <= Hav; i++)
    {
        best = INF;
        if (i <= Num) Ago[i] = inf;
        
        for (int t = 1; t <= i && t <= Num; t++)
        {
            dis = Abs(Team[i].val - Shelt[t].val);
            if (dis < best)
            {
                best = dis;
                pos = t;
            }
            
            if (Ago[t - 1] + dis > Ago[t] + best)
            {
                Now[t] = Ago[t] + best;
                Map[i][t] = pos;
            }
            else
            {
                Now[t] = Ago[t - 1] + dis;
                Map[i][t] = t + INF;
            }
        }
        
        Now[0] = Ago[0] = inf;
        G = Now; Now = Ago; Ago = G;
    }
    
    pos = Num;
    for (int i = Hav; i > 0; i--)
    {
        if (Map[i][pos] > INF)
        {
            Ans[Team[i].id] = Shelt[Map[i][pos] - INF].id;
            pos--;
        }
        else
        {
            Ans[Team[i].id] = Shelt[Map[i][pos]].id;
        }
    }
    
    printf("%lld\n", Ago[Num]);
    for (int i = 1; i < Hav; i++)
    {
        printf("%d ", Ans[i]);
    }
    printf("%d\n", Ans[Hav]);
}

int main()
{
    Read_Case();
    Deal();
    return 0;
}