Codeforces Round #677 (Div. 3) D. Districts Connection思维1200

题目链接 Problem - 1433D - Codeforces

题目

美好的一天，从看不懂题目开始~~

4

5

1 2 2 1 3

3

1 1 1

4

1 1000 101 1000

4

1 2 3 4

YES

1 3

3 5

5 4

1 2

NO

YES

1 2

2 3

3 4

YES

1 2

1 3

1 4

题意

给n个区域，用n-1个路把它们连起来，使每个地方都能到达其它任何地方

但是呢，每个区域都属于一个组织，不能让两个相同的组织直接相连

解析

想到了就很容易过的，比如说拿1当中介，所有的与1不同组织的区域都和1相连，与1同组织的与temp相连

其中temp=“和1非同组织的序号”

AC代码

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

int a[5010];

int main()

{

   int t;

   cin >> t;

   while(t --)

   {

       int n;

       cin >> n;

       int lag = 0;

       for(int i = 1; i <= n; i ++)

       {

            cin >> a[i];

            if(i!= 1 && a[i] != a[1])

                lag = i;

       }

       if(lag==0)

        cout << "NO" << endl;

       else

       {

           cout << "Yes" << endl;

           for(int i = 2; i <= n; i ++)

                if(a[i] != a[1])

                    cout << 1 << ' ' << i << endl;

                else cout << i << ' '<< lag << endl;

       }

   }

    return 0;

}

英语小芝士

district  区域，地方

distinct 不同的，清楚的，明显的

gang  伙，群，组织

输出部分的：

Each road should be presented as a pair of integers xi and yi (1≤xi,yi≤n;xi≠yi1≤xi,yi≤n;xi≠yi), where xi and yi are two districts the i-th road connects.

每条路都应该用一对整数xi,yi表示， xi,yi是不同的区域