使序列有序的最少交换次数

题意很简单,给出一个序列,你可以交换任意两个数字,问最少交换多少次可以使序列有序

NEU1511 Caoshen like math(使序列有序的最小交换次数)

环内的元素个数-1

代码

#define mem(a,b) memset(a,b,sizeof(a))
const int N=1000000+20;
int a[N],vis[N],m[N];
int main()
{
    int n,x;
    while(~scanf("%d",&n))
    {
        mem(a,0);
        mem(vis,0);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            m[a[i]]=i;
        }
        sort(a+1,a+n+1);
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            if(!vis[i])ans++;;
            int j=i;
            while(!vis[j])
            {
                vis[j]=1;
                j=m[a[j]];
            }
        }
        printf("%d\n",n-ans);
    }
    return 0;
}

有N台机器重量各不相等,现在要求把这些机器按照重量排序,重量从左到右依次递增。移动机器只能做交换操作,但交换机器要花费一定的费用,费用的大小就是交换机器重量的和。例如:3 2 1,交换1 3后为递增排序,总的交换代价为4。给出N台机器的重量,求将所有机器变为有序的最小代价。(机器的重量均为正整数)

那么我们可以发现两个环,那么我们回到题目中来,要使最后的总和最小,我们的贪心思路是什么? 一: 对于每一个环的贪心思路就是,找到这个环中最小的那个点,也就是6,然后从6开始进行交换,6和9交换,可以使9到对应的位置,花费为6+9=15,然后6和7交换,花费为6+7=13,最后等到交换完毕,自最后的答案是什么呢?就是: (6+9)+(6+7)+(6+8)=(6+7+8+9)+62=30+12=42 (6+9)+(6+7)+(6+8)=(6+7+8+9)+6*2=30+12=42 剩下一个环不用交换,那么当前的最小值就是42,但是这还不是最优解 二: 我们考虑,在这个图中找到一个最小的值,然后用这个值跟着当前的环进行交换,在这个图中很明显是1,我们让第1和第二个环中的最小值6进行交换,然后再像上面一样,交换1和9,花费为:1+9=10,交换1和7,花费为:1+7=8等到交换完毕,最后的结果是: (1+6)+(1+9)+(1+7)+(1+8)+(1+6)=(6+8+7+9)+15+6=41 (1+6)+(1+9)+(1+7)+(1+8)+(1+6)=(6+8+7+9)+1*5+6=41 所以41比42小,显然41更优,所以我们的贪心策略就是在这两者之间,找出一个最小值

51Nod - 1125 交换机器的最小代价(贪心,思路)

代码

typedef long long ll;
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
const ll N=50000+20;
ll a[N],vis[N];
ll least;
map<ll,ll>m;
ll solve(ll i)
{
    ll j=m[a[i]];
    ll minn=a[i];
    vis[i]=1;
    ll x=0,num=a[i];
    while(i!=j)
    {
        num+=a[j];
        minn=min(minn,a[j]);
        vis[j]=1;
        x++;
        j=m[a[j]];
    }
    printf("x=%d,num=%d\n",x,num);
    return num+min(minn*(x-1),least*(x+2)+minn);
}
int main()
{
    mem(vis,0);
    ll n,x;
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        m[a[i]]=i;
    }
    sort(a+1,a+n+1);
    least=a[1];
    ll ans=0;
    for(ll i=1; i<=n; i++)
    {
        if(!vis[i])
        {
            ans+=solve(i);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

results matching ""

    No results matching ""