如何解决 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';
       }
    }

Answer 2

Where i will be wrong? Here's a link to the code ideone.com/O4ood1

阅读您的代码非常痛苦..您的解决方案并非 100% 正确，因为：

可能有大于 10^10 的非常大的数字，你做错了什么 - 它将这个数字减一直到你达到 n，你的生命太短了等待你的解决方案找到如此大数字的测试结果...（如果你希望 a[i] 变得小于或等于 n，为什么简单不要写 a[i] = n)
```
while(t2>n)
    {
        t2--;
        cnt1++;
    }
```
我运行你的代码在同一个测试用例上两次，但在第二次运行我在测试中更改了给定数字的顺序，您的解决方案显示不同的答案：

我删除了读取字符串以便于调试..所以我提供了没有团队名称的测试

第一个运行测试：

1

10

2 3 4 5 6 7 8 9 7 6

而你的解决方案显示结果是 6（哪里错了回答)

第二个运行: 让我们交换最后两个数字并得到

2 3 4 5 6 7 8 9 6 7

而你的解法显示答案是 8（幸运的是正确答案)
假设有两个未放置的数a[6] = 6和a[9] = 9, 和有两个空位1和8,

您的解决方案将 6 正确两个步，并将 6 放在适当的位置8，然后将9放到1的位置。

如果您从号码的 start 位置到它的 destination 你会看到从 9 到 1 的那一行完全 cover 从 6 到 8 的行...看起来不是最优的。

所以你应该尽量避免这种重叠。

现在画线从6到1和从9到8，没有重叠，现在是最优的。
```
So to avoid overlapping   you can for example to sort rest of your numbers.
```

如何解决 SPOJ 上的 BAISED？

How to solve BAISED on SPOJ?

algorithm

greedy