时间戳

首页 > 解决方案 > 打破 2 组中 1 到 n 个数的排列

c++ - 打破 2 组中 1 到 n 个数的排列

问题描述

问题链接：https ://codeforces.com/contest/1295/problem/E

这个问题表明存在 1 到 n 个数字的排列，使得每个数字只出现一次

例如。对于 n = 3，p = [ 1,2,3] 或 [2,1,3]。

现在对于 p 中的每个排列，对于排列 p的第 i个元素都有一个成本 c i 。每当我将第 i个元素从一组移动到另一组时，我都必须支付 c i。

所以，这个问题要求我在任意位置 k 打破两组排列，使得 1 <= k < n。基本上没有集合应该是空的。现在的条件是 set1 = (1 to k) 的每个元素都应该小于 set2 = (k+1, n)。所以这样做我有两个操作，我可以将一个元素从 set1 移动到 set2，反之亦然。对第 i 个元素执行此操作将花费我 ci 的数量。如果 set1 或 set2 为空，则满足条件。

例如

p = [3,1,2] c = [7,1,4]。

设置 1 = [3,1] & 设置 2 = [2]。所以现在我们可以将 2 从 set2 发送到 set1，最低成本为 4。

有关更多示例，请参阅问题。链接在上面。

我的方法：

对于任何 k，我们需要在 set1 中有 1 到 k 个元素并在 set2 中休息。
因此，让我们从我保持 pfx ans 的每个位置开始i = 1并继续移动直到i = n-1&&。要在每个if
处计算 pfx 数组，我们需要添加成本，因为我们必须将元素转移到，如果它小于然后我们需要减去，因为我们之前想要它，所以我们将它包含在我们的总成本中。但现在我们不希望它成为我们的成本，因为我们拥有价值。同样，如果我有 cur 值，我也计算了每个位置。pos = ip[i] > iset2i

这是我的代码。它通过了许多测试用例，但一直在第 10 位失败。无法理解原因。

请帮忙。

#include <bits/stdc++.h>

#define ll unsigned long long
#define pii pair<int,int>

using namespace std;

int main(void)
{
    ll n , ans, prc3=0;
    cin>>n;
    vector<ll> p(n+1),a(n+1);

    for(ll i=1; i<=n; i++) cin>>p[i];
    for(ll i=1; i<=n; i++) cin>>a[p[i]], prc3 += a[p[i]];

    ll prc1=0, prc2=0;
    ll ans1=INT_MAX, ans2=INT_MAX, ans3=INT_MAX;

    vector<bool> vst(n+1,false);

    for(ll i=1; i<n; i++)
    {
        if(p[i]>i)
        {
            prc1 += a[p[i]];
        }
        else if(p[i]<i)
        {
            prc1 -= a[p[i]];
        }

        if(vst[i])
        {
            prc1 -= a[i];
        }

        vst[p[i]] = true;

        if(!vst[i])
        {
            prc1 += a[i];
        }

        ans1 = min(ans1,prc1);

        prc2 += a[p[i]];

        ans2 = min(ans2,prc2);

        prc3 -= a[p[i]];

        ans3 = min(ans3,prc3);


    }

    ans = min(ans1,ans2);
    ans = min(ans,ans3);

    cout << ans << endl;

    return 0;

}

标签： c++algorithmdynamic-programming

解决方案

我不确定您的代码到底想做什么，但是从我自己解决这个问题并最终阅读社论来看，在我看来，在约束范围内实现解决方案需要树数据结构。

据我了解，我们保留了一个变量 ，k它代表左侧的最高数字。我们从k1 开始，迭代到n. 同时，我们保留一棵树，其中每个键 ,i指向k从位置 开始创建当前分区的成本i。

当我们增加 时k，所有i大于或等于k起始列表中位置的分区起始位置的 s 都不需要移动该元素，因此我们更新所有这些s，使用树及时从每个中i减去；并更新所有指向小于 的分区起始位置的 s，将移动的成本添加到每个位置。我们在每次迭代中取最低成本。A[p[k]]O(log n)ik

据我所知，及时更新段O(log n)需要树数据结构。

推荐阅读