4 条题解

  • 4
    @ 2021-8-7 20:58:02

    C++ :

    #include <iostream>
    using namespace std;
    int n;
    int a[10005];
    long long sum;
    int ffind(){
    	long long min = 20000000000;
    	long long min2 = 20000000000;
    	int pos;
    	int pos2;
    	for(int i=0;i<n;i++){
    		if(a[i]<min){
    			min = a[i];
    			pos = i;
    		}
    		
    	}
    	a[pos] = 9999999999;
    	for(int i=0;i<n;i++){
    		if(a[i]<min2){
    			min2 = a[i];
    			pos2 = i;
    		}
    		
    	}
    	a[pos2] = min+min2;
    	return min+min2;
    }
    int main(){
    
    	cin>>n;
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	for(int i=0;i<n-1;i++){
    		sum += ffind();
    	}
    	cout<<sum<<endl;
    	return 0;
    }
    
    • 0
      @ 2025-4-9 20:21:17

      #include using namespace std; int n; int a[10005]; long long sum; int ffind(){ long long min = 20000000000; long long min2 = 20000000000; int pos; int pos2; for(int i=0;i<n;i++){ if(a[i]<min){ min = a[i]; pos = i; }

      }
      a[pos] = 9999999999;
      for(int i=0;i<n;i++){
      	if(a[i]<min2){
      		min2 = a[i];
      		pos2 = i;
      	}
      	
      }
      a[pos2] = min+min2;
      return min+min2;
      

      } int main(){

      cin>>n;
      for(int i=0;i<n;i++)
      	cin>>a[i];
      for(int i=0;i<n-1;i++){
      	sum += ffind();
      }
      cout<<sum<<endl;
      return 0;
      

      }

      • 0
        @ 2024-9-8 19:55:41

        AC代码:

        #include<iostream>
        #include<cstdio>
        #include<cstdlib>
        #include<cstring>
        #include<algorithm>
        using namespace std;
        
        typedef long long LL;
        
        const int N=300005;
        
        int n,m,tot,mo1[20],mo2[20],ans[20],p[N],w[N],c[N],jc[N],ny[N],num[N],now,t[N],po[N];
        
        void divi()
        {
            int x=m;
            for (int i=2;i*i<=x;i++)
                if (x%i==0)
                {
                    mo1[++tot]=1;mo2[tot]=i;
                    while (x%i==0) mo1[tot]*=i,x/=i;
                }
            if (x>1) mo1[++tot]=x,mo2[tot]=x;
        }
        
        void ins(int x,int y)
        {
            while (x<=n) c[x]+=y,x+=x&(-x);
        }
        
        int find(int x)
        {
            int ans=0;
            while (x) ans+=c[x],x-=x&(-x);
            return ans;
        }
        
        int ksm(int x,int y)
        {
            int ans=1;
            while (y)
            {
                if (y&1) ans=(LL)ans*x%mo1[now];
                x=(LL)x*x%mo1[now];y>>=1;
            }
            return ans;
        }
        
        void solve()
        {
            for (int i=1;i<=n;i++) t[p[i]]++;
            jc[0]=ny[0]=po[0]=1;
            for (int i=1;i<=n;i++)
            {
                po[i]=(LL)po[i-1]*mo2[now]%mo1[now];
                int x=i;num[i]=0;
                while (x%mo2[now]==0) x/=mo2[now],num[i]++;
                jc[i]=(LL)jc[i-1]*x%mo1[now];num[i]+=num[i-1];
                ny[i]=ksm(jc[i],mo1[now]/mo2[now]*(mo2[now]-1)-1);
            }
            int sum=num[n],val=jc[n];
            for (int i=1;i<=n;i++) sum-=num[t[i]],val=(LL)val*ny[t[i]]%mo1[now],ins(p[i],1);
            for (int i=1;i<=n;i++)
            {
                val=(LL)val*ny[n-i+1]%mo1[now]*jc[n-i]%mo1[now];sum+=num[n-i]-num[n-i+1];
                int s=find(p[i]-1);
                (ans[now]+=(LL)val*s%mo1[now]*po[sum]%mo1[now])%=mo1[now];
                ins(p[i],-1);
                val=(LL)val*jc[t[p[i]]]%mo1[now]*ny[t[p[i]]-1]%mo1[now];
                sum+=num[t[p[i]]]-num[t[p[i]]-1];
                t[p[i]]--;
            }
        }
        
        int merge()
        {
            int s=0;
            for (int i=1;i<=tot;i++)
                now=i,(s+=(LL)ans[i]*(m/mo1[i])%m*ksm(m/mo1[i],mo1[i]/mo2[i]*(mo2[i]-1)-1)%m)%=m;
            return s;
        }
        
        int main()
        {
            scanf("%d%d",&n,&m);
            for (int i=1;i<=n;i++) scanf("%d",&p[i]),w[i]=p[i];
            sort(w+1,w+n+1);int w1=unique(w+1,w+n+1)-w-1;
            for (int i=1;i<=n;i++) p[i]=lower_bound(w+1,w+w1+1,p[i])-w;
            divi();
            for (int i=1;i<=tot;i++) now=i,solve();
            printf("%d",(merge()+1)%m);
            return 0;
        }
        
        • -1
          @ 2021-11-7 22:06:37
          #include<iostream>
          #include<cstdio>
          #include<cmath>
          #include<cstdlib>
          #include<cstring>
          #include<algorithm>
          #include<queue>
          #include<vector>
          using namespace std;
          priority_queue <int,vector<int>,greater<int> > q;
          int main(){
              int n;
              cin>>n;
              for(int i=1;i<=n;i++){
                  int x;
                  cin>>x;
                  q.push(x);
              }
              long long ans=0;
              while(--n){
                  int t = 0;
                  t += q.top();
                  q.pop();
                  t += q.top();
                  q.pop();
                  ans += t;
                  q.push(t);
              }
              cout<<ans;
              return 0;
          }
          
          • 1

          信息

          ID
          59
          时间
          1000ms
          内存
          256MiB
          难度
          9
          标签
          递交数
          249
          已通过
          16
          上传者