baidu差最小的有多少对呢?差最大呢?

xiaoxiao2021-02-28  135

//小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差最小的有多少对呢?差最大呢? #include<bits/stdc++.h> using namespace std; int main() {     int n;     while(cin>>n)     {         int i,j,x;         map<int,int>a;         map<int,int>::iterator it;         map<int,int>::iterator it1;         for(i=0; i<n; i++)         {             cin>>x;             a[x]++;         }         vector<int>b;         for(it=a.begin(); it!=a.end(); it++)             {                 b.push_back(it->first);             }         int min=0,max=0;         if(a.size()==1)         {             min=max=n*(n-1)/2;         }         else if(a.size()==n)         {             int M=1<<30;             for(it=a.begin(); it!=a.end(); it++)             {                 it1=++it;                 it--;                 if(it1!=a.end())                     if(M>it1->first-it->first)M=it1->first-it->first;             }             for(it=a.begin(); it!=a.end(); it++)             {                 it1=++it;                 it--;                 if(it1!=a.end())                     if(M==it1->first-it->first)min++;             }             max=1;         }         else         {             it=a.end();             it--;             max=a.begin()->second*it->second;             for(it=a.begin(); it!=a.end(); it++)             {                 if(it->second>1)                 {                     min+=it->second*(it->second-1)/2;                 }             }         }         cout<<min<<" "<<max<<endl;         /*         for(it=a.begin(); it!=a.end(); it++)             {                 cout<<it->first<<" "<<it->second<<endl;             }             */     }     return 0; }
转载请注明原文地址: https://www.6miu.com/read-39897.html

最新回复(0)