题目链接

链接

题目大意

有n个座位，给一个数列，1代表有人，0代表没人，让所有人坐到其他没人的地方去，移动的花费是位置的差值，问你最少的花费是多少？

题解

这道题第一个想法是把第一个人安排到自己前面所有空的地方，然后就有很多种安排方法，然后第二个人再安排到第二个人前面的座位上，不要安排到钱一个人的前面就行，然后来计算最小花费。好像这种实现方法比较繁琐，然后就采取下面的方法。

• fi代表前i个人前j个座位有人坐的最小花费。
• 当前人坐座位f[i][j] = f[i - 1][j - 1]
• 当前人不坐座位f[i][j] = f[i][j - 1]

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 5010;
int a[N], b[N];
int f[N][N];
void solve()
{
    int n;
    cin >> n;
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(x) a[++cnt1] = i;
        else b[++cnt2] = i;
    }
    for(int i = 1; i <= cnt1; i++){
        for(int j = 1; j <= cnt2; j++){
            if(i == j){
                f[i][j] = f[i - 1][j - 1] + abs(a[i] - b[j]);//前i个人不可能坐到前j-1个椅子上，人数不能少于椅子数量
            }
            else{
                f[i][j] = min(f[i][j - 1], f[i - 1][j - 1] + abs(a[i] - b[j]));
            }
        }
    }
    cout << f[cnt1][cnt2] << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}