题目链接：http://codeforces.com/contest/1283/problem/D

题意：给你n棵树在数轴上的坐标。有m个人，要你把这m个人放在数轴上，一个点只能放一个人（树所在的点不能放）。要使得这m个人每个人到离他最近的树的距离（以下统称距离）的总和最小，输出这个最小值以及m个人在数轴上的坐标。

解法一：BFS

       我看过网上大部分人思路是跑BFS，因为假设树坐标是x，那我肯定是放 x+1,x-1,x+2,x-2,...这样最优的，所以我用map记录这个点有没有被放过，然后广搜的去放人就ok了。

AC代码

 1 //#include<bits/stdc++.h>
 2 #include<set>
 3 #include<map>
 4 #include<stack>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<queue>
 8 #include<cstdio>
 9 #include<string>
10 #include<vector>
11 #include<cstdlib>
12 #include<cstring>
13 #include<iostream>
14 #include<algorithm>
15 #include<unordered_map>
16 using namespace std;
17 typedef long long ll;
18 typedef unsigned long long ull;
19 typedef pair<int, int> pii;
20 typedef pair<ll, ll> pll;
21 typedef pair<ll, int> pli;
22 typedef pair<int, ll> pil;
23 #define X first
24 #define Y second
25 #define pb push_back
26 inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
27 inline ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
28 inline ll lowbit(ll x) { return x & (-x); }
29 const double PI = 3.14159265358979323846;
30 const int inf = 0x3f3f3f3f;
31 const ll INF = 0x3f3f3f3f3f3f3f3f;
32 const ll mod = 998244353;
33 inline char nc() {
34     static char buf[1 << 21], * p1 = buf, * p2 = buf;
35     return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
36 }
37 inline ll rd() {
38     //#define getchar nc
39     ll x = 0, f = 1; char ch = getchar();
40     while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
41     while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
42     return x * f;
43 }
44 const double eps = 1e-8;
45 const int M = 2e5 + 10;
46 const int N = 1e6 + 10;
47 int a[N];
48 int n, m;
49 queue<pii>q;
50 map<int, bool>vis;
51 ll ans = 0;
52 vector<int>ver;
53 void bfs() {
54     while (m > 0) {
55         pii st = q.front(); q.pop();
56         if (!vis.count(st.X - 1)) {
57             ans += 1ll * st.Y + 1;
58             q.push({ st.X - 1,st.Y + 1 });
59             vis[st.X - 1] = 1;
60             ver.pb(st.X - 1);
61             m--;
62         }
63         if (m == 0)break;
64         if (!vis.count(st.X + 1)) {
65             ans += 1ll * st.Y + 1;
66             q.push({ st.X + 1,st.Y + 1 });
67             vis[st.X + 1] = 1;
68             ver.pb(st.X + 1);
69             m--;
70         }
71     }
72 }
73 int main() {
74     n = rd(), m = rd();
75     for (int i = 1; i <= n; i++) {
76         a[i] = rd();
77         vis[a[i]] = 1;
78         q.push({ a[i],0 });
79     }
80     bfs();
81     printf("%lld\n", ans);
82     for (auto& val : ver) {
83         printf("%d ", val);
84     }
85     puts("");
86 }
View Code

解法二:  二分+模拟

        先说这个做法的代码实现的确较烦一点，但是也不失是一种以后值得运用的思维方式。我们考虑距离最大的人的值是多少，因为试想如果距离最大的人确定下来了我们假设为x，那么对于这n课树，所有距离他小于x的并且能放人的点必定都会被放上人（贪心原理），然后我们还有 （m-已经放好的人数） 个人未放，这些人到树的距离必定都是x，所以接下来就相当于模拟题一样，把剩下的人放掉就好了。所以我们关键在于如何去确定这个最小的x是多少，换言之 距离最大的人最小是多少，对于这种最大值求最小的，我们显然可以用二分。我们先将n课树的坐标按升序进行排序。每次的check，我们贪心的去放这m个人就可以了。

而且最重要的是，这样写代码跑的速度比一种方法快了不只一倍（虽然复杂度是一样的），但是对于我这种十分看重代码速度的人来说，心里不要多舒服。^-^

AC代码

//#include<bits/stdc++.h>
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair < int,int>
#define pll pair < ll , ll >
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
inline ll lowbit(ll x) { return x & (-x); }
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
inline ll rd() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const double eps = 1e-8;
const int M = 4e6 + 10;
const int N = 1e6 + 10;
int a[N];
vector<int>mp[N];
int n, m;
bool check(int x) {
    int ma = -inf;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += min(a[i] - ma - 1, x);
        sum += min(a[i + 1] - a[i] - 1, x);
        ma = min(a[i + 1] - 1, a[i] + x);
        if (sum >= m)return 1;
    }
    return 0;
}
int main() {
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++)a[i] = rd();
    sort(a + 1, a + 1 + n);
    a[0] = -inf;
    a[n + 1] = inf;
    int l = 1, r = m;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    int dis = l - 1;
    ll ans = 0;
    int ma = -inf;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = max(ma + 1, a[i] - dis); j <= a[i] - 1; j++)
            ans += abs(j - a[i]), cnt++, mp[i].push_back(j);
        for (int j = a[i] + 1; j <= min(a[i + 1] - 1, a[i] + dis); j++)
            ans += min(abs(j - a[i]), abs(j - a[i + 1])), cnt++, mp[i].push_back(j);
        ma = min(a[i + 1] - 1, a[i] + dis);
    }
    ans += ((ll)m - cnt) * ((ll)dis + 1);
    int res = m - cnt;
    for (int i = 1; i <= n; i++) {
        int x, l, r, y;
        if (mp[i - 1].size())
            x = max(a[i - 1], mp[i - 1][mp[i - 1].size() - 1]);
        else
            x = a[i - 1];
 
        if (mp[i].size())
            l = min(mp[i][0] - 1, a[i] - 1), r = max(mp[i][mp[i].size() - 1] + 1, a[i] + 1);
        else
            l = a[i] - 1, r = a[i] + 1;
 
        if (mp[i + 1].size())
            y = min(a[i + 1], mp[i + 1][0]);
        else
            y = a[i + 1];
 
        if (l > x)
            res--, mp[i - 1].push_back(l);
        if (res == 0)break;
        if (r < y)
            res--, mp[i].push_back(r);
        if (res == 0)break;
    }
    printf("%lld\n", ans);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < mp[i].size(); j++) {
            printf("%d ", mp[i][j]);
        }
    }
    printf("\n");
}
View Code