Educational Codeforces Round 109 (Rated for Div. 2) - D. Armchairs

Solost

2023 年 05 月 17 日

199 次浏览

暂无评论

1138字数

题目题解

## 题目链接

[链接](https://codeforces.com/problemset/problem/1525/D)

## 题目大意

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

## 题解

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

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

```cpp
#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;
}

```

最后修改：2023 年 05 月 17 日