互相送礼物

https://codeforces.com/contest/1283/problem/C

题意:n个人相互送礼物,每个只能送一份礼物且接收一份礼物,不能自己送自己。

给出n个数,0代表第i个人不知道送礼物给谁(最少有两个0)。要求给出完整的n人送礼物方案。

解法:两个数组分别储存谁没收到礼物和谁不知道送礼物给谁。通过不能自己送自己这一条件,

进行调整。

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF  0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
using namespace std;
typedef long long ll ;
int f[200009];//原数组谁给了谁。
int vis[200009] ;//标记谁收到了礼物
int a[200009] ;//存储谁没收到了礼物
int g[200009];//存储谁不知道把礼物送给谁

int main()
{
    int n ;
    scanf("%d" , &n);
    int cnt = 0 ;
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d" , &f[i]);
        if(f[i]) vis[f[i]] = 1;
        else g[cnt++] = i ;
    }
    cnt = 0 ;
    for(int i = 1 ; i <= n ; i++)
    {
        if(!vis[i]) a[cnt++] = i ;
    }
    for(int i = 0 ; i < cnt ; i++)
    {
        if(a[i] == g[i])
        {
            swap(a[i] , a[cnt-1]);
        }
    }
    if(a[cnt-1] == g[cnt-1]) swap(a[cnt-1] , a[0]);
    for(int i = 0 ; i < cnt ; i++)
    {
        f[g[i]] = a[i];
    }
    for(int i = 1 ; i < n ; i++)
    {
        cout << f[i] << " "  ;
    }
    cout << f[n] << endl ;

    return 0 ;
}

 

原文链接: https://www.cnblogs.com/nonames/p/12238157.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    互相送礼物

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/325653

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月1日 下午3:25
下一篇 2023年3月1日 下午3:26

相关推荐