Maximum Balanced Circle-白红宇

Maximum Balanced Circle

阅读量：2038 次

发布时间：2019-04-28

本文共 1295 字，大约阅读时间需要 4 分钟。

题意：求一个相邻元素之间绝对值为小于1的最大环

题解：

1、桶排序；

2、环肯定在没有或者数量为1的元素之间；

/**@Author:   STZG*@Language: C++*/#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   //#define DEBUG#define RI register int#define endl "\n"using namespace std;typedef long long ll;//typedef __int128 lll;const int N=200000+10;const int M=100000+10;const int MOD=1e9+7;const double PI = acos(-1.0);const double EXP = 1E-8;const int INF = 0x3f3f3f3f;int t,n,m,k,p,l,r,u,v;int ans,cnt,flag,temp,sum;int a[N],b[N],c[N];char str;struct node{};int main(){#ifdef DEBUG freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout);#endif //ios::sync_with_stdio(false); //cin.tie(0); //cout.tie(0); //scanf("%d",&t); //while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[a[i]]++; } l=0; r=0; temp=0; ans=0; int L=0,R=0; for(int i=1;i<=200000;i++){ if(b[i]){ //cout<
                   <
                    
                     =2){ temp+=b[i]; r++; }else{ temp+=b[i]; if(temp>ans){ L=l; R=i; ans=temp; } l=i; r=i; temp=b[i]; } }else{ temp+=b[i]; if(temp>ans){ L=l; R=i; ans=temp; } l=i; r=i; temp=b[i]; } } if(temp>ans){ L=l; R=n+1; ans=temp; } //cout<
                     
                      <<" "<
                      
                       <
                       
                        L;i--){ for(int j=1;j<=b[i]/2;j++){ c[++cnt]=i; } } cout<
                        
                         <