fork(6) download
copy 
  1. #include <iostream>
  2. #define INT_MAX 2147483647
  3. using namespace std;
  4.  
  5. struct wskaznik
  6. {
  7.     int wartosc;
  8.     int indeks;
  9. };
  10.  
  11. void lowestelement(int A[],int na, wskaznik &pierwszy, wskaznik &drugi)
  12. {
  13.     pierwszy.wartosc=INT_MAX;
  14.     drugi.wartosc=INT_MAX;
  15.     pierwszy.indeks=0;
  16.     drugi.indeks=1;
  17.     for(int i=0; i<na; i++)
  18.     {
  19.         if(A[i]<pierwszy.wartosc)
  20.         {
  21.             drugi.wartosc=pierwszy.wartosc;
  22.             drugi.indeks=pierwszy.indeks;
  23.             pierwszy.wartosc=A[i];
  24.            pierwszy.indeks=i;
  25.         }
  26.         else if(A[i] < drugi.wartosc )
  27.             {
  28.             drugi.wartosc=A[i];
  29.             drugi.indeks=i;
  30.             }
  31.     }
  32. }
  33.  
  34.  
  35. int main()
  36. {
  37.     ios_base::sync_with_stdio(0);
  38.     cin.tie(0);
  39.     int t;
  40.     int n;
  41.     int a,b;
  42.     //int w=0;
  43.     int* tab;
  44.     int *tabindeks;
  45.     wskaznik pierwszy;
  46.     wskaznik drugi;
  47.     long long suma=0;
  48.     cin>>t;
  49.     for(int i=0; i<t; i++)
  50.     {
  51.         cin>>n;
  52.         tab=new int [n];
  53.         for (int j=0; j<n; j++)
  54.         {
  55.             cin>>tab[j];
  56.         }
  57.         tabindeks=new int[2*n-2];
  58.         for(int j=0; j<n-1; j++)
  59.         {
  60.             lowestelement(tab,n,pierwszy,drugi);
  61.             a=min(pierwszy.indeks,drugi.indeks);
  62.             b=max(pierwszy.indeks,drugi.indeks);
  63.             suma=suma+pierwszy.wartosc+drugi.wartosc;
  64.             tabindeks[2*j]=a;
  65.             tabindeks[2*j+1]=b;
  66.             tab[a]=(pierwszy.wartosc)+(drugi.wartosc);
  67.             tab[b]=INT_MAX;
  68.         }
  69.         cout<<suma<<endl;
  70.         for(int j=0;j<n-1;j++)
  71.         {
  72.         cout<<tabindeks[2*j]+1<<" "<< tabindeks[2*j+1]+1<<endl;
  73.         }
  74.  
  75.  
  76.         suma=0;
  77.         delete[] tab;
  78.         delete [] tabindeks;
  79.     }
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 4340KB
comments (?)
stdin
copy 
1
10
17 40 58 26 81 36 36 28 28 8
stdout
copy 
1125
1 10
1 4
8 9
6 7
1 2
3 8
5 6
1 3
1 5
https://ideone.com/VFkjpX
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!