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;
    }
    
    • 1
      @ 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;
      }
      
      • 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;
        

        }

        • -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
          标签
          递交数
          251
          已通过
          17
          上传者