algorithm - 如何解决 SPOJ 上的 BAISED？

Question

我正在尝试解决这个 SPOJ 问题 http://www.spoj.com/problems/BAISED/ .

我的方法

for all elements in the preferred_position array
 if(position>0&&position<=n)
    if(position is unoccupied)
       allocate position for user
 else
   reach the first free position in the array

for all elements whose preferred position is already filled
    search both directions left,right to find nearest free_position

我尝试了很多测试用例并得到了正确的结果，但我不知道我在哪里失败并得到了错误的答案。我根据贪婪标签选择了这个问题，我真的不知道在哪里应用贪婪技术。任何人都可以提出一些建议吗？

Answer 1

这是我接受的解决方案!!

我发送了几次，直到意识到数字可能非常大，所以我将所有内容都更改为 long long

简单地对数字进行排序，然后找出它们位置之间的差异。

我是如何找到这个解决方案的:

1) you should place all teams in positions from 0 to n - 1

2) lets place as many teams as possible in their preferred places

3) rest unplaced teams have the same preferred positions as placed teams or preferred positions are large then n - 1 (or n - if enumerated from 1)

4) As we remember that we need to fell all positions from 0 to n - 1, so it is obvious that if we sort the unplaced teams we could minimize the answer

为什么我跳过第二步(你可以尝试证明)，让我们看一下示例测试:

1
3
first team 2
second team 3
third team 4
4 2 3 -> |1 - 4| + |2 - 2| + |3 - 3| = 3
2 3 4 -> |1 - 2| + |2 - 3| + |3 - 4| = 3

    #include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;
    int main() {
        ios::sync_with_stdio(false);
        long long t;
        cin >> t;
        vector <long long> a;
        for (long long i = 0; i < t; i++) {
           long long n;
           cin >> n;
            a.clear();
            for (long long j = 0; j < n; j++) {
                string s;
                cin >> s;
                long long p ;
                cin >> p;
                p--;
                a.push_back(p);
            }
            sort(a.begin(), a.end());
            long long ans = 0;
            for (long long i = 0; i < a.size(); i++) {

                ans += abs(a[i] - i);
            }
            cout << ans << '\n';
       }
    }