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

Question

Closed. This question needs debugging details。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为 on-topic用于堆栈溢出。

在4个月前关闭。



Improve this question




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

此问题表明存在1到n个数字的排列，因此每个数字仅出现一次

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

现在，对于p中的每个置换，置换p的第i个元素的成本为ci。每当我将第i个元素从一组移到另一组时，我都必须支付ci。

因此，该问题要求我在任意位置k上将置换分解为两组，使得1 <= k
例如

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

set1 = [3,1] & set2 = [2]. so now we can send 2 from set2 to set1 with minimum cost of 4.

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

我的方法:

for any k we need to have 1 to k element in set1 and rest in set2.
So lets start from i = 1 and keep on moving till i = n-1 && at every position I maintain the pfx ans.
To calculate the pfx array at every pos = i if the p[i] > i then we need to add the cost because we have to transfer the element to set2 and if it is less than i then we need to substract because we wanted it before so we had it in our total cost. but now we don't want it to be in our cost since we have the value. similarly I have also calculated for every position if I had the cur value or not.

这是我的代码。它通过了许多测试用例，但在第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;

}

最佳答案

我不确定您的代码到底想做什么，但是我自己努力解决这个问题并最终阅读editorial，对我来说，在约束内实现解决方案似乎需要树数据结构。

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

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

据我所知，在O(log n)时间段上的更新将需要树数据结构。

关于c++ - 2组中从1到n的数字的打破排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61467755/

上一篇：math - float 学运算是否被破坏？

下一篇：c++ - c++:每次打印 vector 时，如何打印 vector 元素的索引？

相关文章：

java - 编辑距离代码中的 NZEC

c - 采访中询问: Dynamic Programming

python - 动态规划 - 使用一组整数计算总和的方法数

c++ - 如何处理多个迭代器类型

c++ - 如何动态创建状态机

c++ - 为什么这个 multiset 打印代码会导致永远循环？

生产者消费者上的Java多线程

c++ - 在 C++ 中实现随机 oracle(输出在范围内是随机的，但相同输入的输出相同)

c++ - 如何使用环境变量添加现有项目？

algorithm - 如何保证基于哈希的ID的唯一性？

Answer 1

我不确定您的代码到底想做什么，但是我自己努力解决这个问题并最终阅读editorial，对我来说，在约束内实现解决方案似乎需要树数据结构。

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

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

据我所知，在O(log n)时间段上的更新将需要树数据结构。