首页 > 代码库 > codevs4437 YJQ Arranges Sequences

codevs4437 YJQ Arranges Sequences

题目描述 Description

神犇YJQ有两个长度均为n的数列A和B,并且A是一个单调不增的数列。他认为这两个数列的优美度为技术分享。有一天YJQ很无聊,他把Bi进行重新排列,得到了许多不同的优美度。他想知道他能得到的最大的优美度和最小的优美度的差是多少。

 

输入描述 Input Description

第一行一个整数n表示数列长度,接下来n行每行两个整数表示Ai和Bi

输出描述 Output Description

一行,一个整数表示优美度的最大值与最小值的差

样例输入 Sample Input

2
2 1
1 2

样例输出 Sample Output

1

数据范围及提示 Data Size & Hint

对于30%的数据,n < 10;

对于50%的数据,n < 1000;

对于100%的数据,1 < n < 2 *10^5,1< Ai,Bi < 10^9。

请注意数据范围!!!!!!!!!!!!!!!!!!!

注意:10^5*10^9*10^9>18446744073709551615(Unsigned  Long Long的最大值)

#include <cstdio> #include <cmath> #include <iostream> #include <cstring> #include <algorithm>#define ll long longusing namespace std;  const int P=10000,L=10,W=4; char s[L*W]; struct Big   {     int len;int data[L];bool fu;     void clear()        {         memset(data,0,sizeof(data));         len=0;fu=false;       }     int& operator [] (int k)       {         return data[k];       }     void operator = (int k)       {         clear();         if (k<0) fu=true,k=-k;else fu=false;         len=0;         while (k) data[++len]=k%P,k/=P;          if (len==0) len=1;       }     bool operator < (Big b)       {         bool t=false;         if (fu && !b.fu) return true;         if (!fu && b.fu) return false;         if (fu && b.fu) t=true;         if (len<b.len) return true^t;         if (len>b.len) return false^t;         for (int i=len;i;--i)           {             if (data[i]<b[i]) return true^t;             if (data[i]>b[i]) return false^t;           }         return false;       }     bool operator <= (Big b)       {         bool t=false;         if (fu && !b.fu) return true;         if (!fu && b.fu) return false;         if (fu && b.fu) t=true;         if (len<b.len) return true^t;         if (len>b.len) return false^t;         for (int i=len;i;--i)           {             if (data[i]<b[i]) return true^t;             if (data[i]>b[i]) return false^t;           }         return true;       }     bool operator > (Big b)       {         bool t=false;         if (fu && !b.fu) return false;         if (!fu && b.fu) return true;         if (fu && b.fu) t=true;         if (len<b.len) return false^t;         if (len>b.len) return true^t;         for (int i=len;i;--i)           {             if (data[i]<b[i]) return false^t;             if (data[i]>b[i]) return true^t;           }         return false;       }     bool operator >= (Big b)       {         bool t=false;         if (fu && !b.fu) return false;         if (!fu && b.fu) return true;         if (fu && b.fu) t=true;         if (len<b.len) return false^t;         if (len>b.len) return true^t;         for (int i=len;i;--i)           {             if (data[i]<b[i]) return false^t;             if (data[i]>b[i]) return true^t;           }         return true;       }     bool operator == (Big b)       {         if (fu!=b.fu) return false;         if (len<b.len) return false;         if (len>b.len) return false;         for (int i=len;i;--i)           if (data[i]!=b[i]) return false;         return true;       }     bool operator == (int k)       {         if (k<0)           {             if (!fu) return false;             k=-k;           } else if (fu) return false;         if (k>=P)           {             Big b;b=k;             return *this==b;           }             else return len==1 && data[1]==k;       }     bool operator != (Big b)       {         if (fu!=b.fu) return true;         if (len<b.len) return true;         if (len>b.len) return true;         for (int i=len;i;--i)           if (data[i]!=b[i]) return true;         return false;       }     bool operator != (int k)       {         if (k<0)           {             if (!fu) return true;             k=-k;           } else if (fu) return true;         if (k>=P)           {             Big b;b=k;             return *this!=b;           }             else return !(len==1 && data[1]==k);       }     Big operator + (Big b)       {         Big a=*this,c;c.clear();         if (a.fu && b.fu)            {             a.fu=false;b.fu=false;c=a+b;             if (c.len!=1 || c[1]!=0) c.fu=true;             return c;           }         if (a.fu && !b.fu)            {a.fu=false;return b-a;}         if (!a.fu && b.fu)           {b.fu=false;return a-b;}          a.len=max(a.len,b.len);         for (int i=1;i<=a.len;++i)           {             a[i+1]+=(a[i]+b[i])/P;             a[i]=(a[i]+b[i])%P;           }         if (a[a.len+1]) ++a.len;         while (a[a.len]==0 && a.len>1) --a.len;         return a;       }     Big operator + (int k)       {         Big a=*this,b;b=k;         return a+b;       }     Big operator - (Big b)       {         Big a=*this,c;c.clear();         if (a.fu && !b.fu)           {             a.fu=false;b.fu=false;c=a+b;             if (c.len!=1 || c[1]!=0) c.fu=true;             return c;           }         if (a.fu && b.fu)            {             a.fu=false;b.fu=false;return b-a;           }         if (!a.fu && b.fu)           {             b.fu=false; return a+b;           }         if (a<b) swap(a,b),a.fu=true;else a.fu=false;         for (int i=1;i<=a.len;++i)           {             if (a[i]<b[i]) a[i]+=P,--a[i+1];             a[i]-=b[i];           }         while (a[a.len]==0 && a.len>1) --a.len;         if (a.len==1 && a[1]==0) a.fu=false;         return a;       }     Big operator - (int k)       {         Big a=*this,b;b=k;         return a-b;       }     Big operator * (Big b)       {         Big c;c.clear();         c.len=len+b.len-1;         for (int i=1;i<=len;++i)           for (int j=1;j<=b.len;++j)             {               c[i+j-1]+=data[i]*b[j];               c[i+j]+=c[i+j-1]/P;               c[i+j-1]%=P;             }         if (c[c.len+1]) ++c.len;         while (c[c.len]==0 && c.len>1) --c.len;         c.fu=fu^b.fu;         if (c.len==1 && c[1]==0) c.fu=false;         return c;       }     Big operator * (int k)       {         Big a=*this;         if (k<0) a.fu=!a.fu,k=-k;         if (k>=P)            {             Big b;b=k;             return a*b;           }         for (int i=1;i<=a.len;++i) a[i]*=k;         for (int i=1;i<=a.len;++i)           a[i+1]+=a[i]/P,a[i]%=P;         while (a[a.len+1])            {             ++a.len;             a[a.len+1]=a[a.len]/P;             a[a.len]%=P;           }         while (a[a.len]==0 && a.len>1) --a.len;         if (a.len==1 && a[1]==0) a.fu=false;         return a;       }     Big operator / (int k)       {         Big a=*this;int g=0;         if (k<0) a.fu=!a.fu,k=-k;         for (int i=a.len;i;--i)           {             a[i]+=g*P;             g=a[i]%k;             a[i]/=k;           }         while (a[a.len]==0 && a.len>1) --a.len;         if (a.len==1 && a[1]==0) a.fu=false;         return a;       }     Big operator % (int k)       {         Big b;b=k;         return *this%b;       }     Big operator / (Big b)       {         Big c,d;c=0;d=0;c.fu=fu^b.fu;b.fu=false;         for (int i=len;i;--i)           {             d=d*P+data[i];             int ans=0,l=0,r=P-1;             while (l<=r)               {                 int mid=(l+r)>>1;                 if (b*mid<=d) ans=mid,l=mid+1;                 else r=mid-1;               }             c[i]=ans;             d=d-b*c[i];           }         c.len=len;         while (c[c.len]==0 && c.len>1) --c.len;         return c;       }     Big operator % (Big b)       {         Big c,d;c=0;d=0;c.fu=fu^b.fu;b.fu=false;         for (int i=len;i;--i)           {             d=d*P+data[i];             int ans=0,l=0,r=P-1;             while (l<=r)               {                 int mid=(l+r)>>1;                 if (b*mid<=d) ans=mid,l=mid+1;                 else r=mid-1;               }             c[i]=ans;             d=d-b*c[i];           }         c.len=len;         while (c[c.len]==0 && c.len>1) --c.len;         d=*this-b*c;         return d;       }     Big operator ^ (int t)       {         Big a=*this,ans;ans=1;         while (t)           {             if (t&1) ans=ans*a;t>>=1;a=a*a;           }         return ans;       }         void read()       {         scanf("%s",s);         clear();         len=1;         int pow=1,t=1,l=strlen(s),stop=0;         if (s[0]==-) fu=true,stop=1;         for (int i=l-1;i>=stop;--i)           {             if (t>W) t=pow=1,++len;             data[len]+=pow*(s[i]-0);             ++t,pow*=10;           }       }     void write()       {         if (fu) printf("%c",-);         printf("%d",data[len]);         for (int i=len-1;i;--i)           {             if (data[i]<10) putchar(0);             if (data[i]<100) putchar(0);             if (data[i]<1000) putchar(0);             printf("%d",data[i]);           }       }     void writeln()       {         write();printf("\n");       }   } ;inline long long read(){    ll x=0,f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}Big ansa,ansb,ansd,ansc;long long a[200005],b[200005],n;int main(){    cin>>n;    for(int i = 1;i <= n;i++){        a[i] = read();        b[i] = read();    }    sort(b+1,b+1+n);    for(int i = 1;i <= n;i++){        ansd = a[i];        ansb = ansd *(b[n-i+1] - b[i]);        ansc = ansc + ansb;    }    ansc.write();    return 0;}

 

codevs4437 YJQ Arranges Sequences