Numbers(CodeForces-128D)【思维/list】

题目链接：https://vjudge.net/problem/CodeForces-128D

题意：给出一组数，要求将这些数排列成一个环，满足每相邻两个数的差值为1，问能否完成。

思路：先取出最小的数min，作为环中一点，则如果能够完成排列，该数两侧的数字即为min+1，如果min有多个，则放在min+1旁边，重复这样的过程，使用list可以很容易地完成。

代码如下：

 #include<cstdio>

 #include<list>

 #include<iostream>

 #include<cmath>

 #include<unordered_map>

 using namespace std;

 int n,arr[],book[];

 unordered_map<int,int> mp;

 int main(){

     scanf("%d",&n);

     int ha=,minVal=;

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

         scanf("%d",&arr[i]);

         minVal=min(minVal,arr[i]);

         if(mp[arr[i]]==)

             mp[arr[i]]=++ha;

         book[mp[arr[i]]]++;

     }

     int ans=;

     list<int> lt;

     lt.push_front(minVal);

     book[mp[minVal]]--;

     int tmpFro=minVal,tmpBac=minVal,nn=n-;

     while(){

         if(book[mp[tmpFro+]]){

             book[mp[tmpFro+]]--;

             lt.push_front(tmpFro+);

             nn--;

             if(book[mp[tmpFro]]){

                 book[mp[tmpFro]]--;

                 lt.push_front(tmpFro);

                 nn--;

             }

             else tmpFro++;

         }

         if(book[mp[tmpBac+]]){

             book[mp[tmpBac+]]--;

             lt.push_back(tmpBac+);

             nn--;

             if(book[mp[tmpBac]]){

                 book[mp[tmpBac]]--;

                 lt.push_back(tmpBac);

                 nn--;

             }

             else tmpBac++;

         }

         else break;

     }

     if(nn==&&abs(*lt.begin()-*lt.rbegin())==){

         printf("YES");

     }

     else printf("NO");

     return ;

 }

By xxmlala

巴特西

Numbers(CodeForces-128D)【思维/list】

最新文章

热门文章