[UVA] 120 - Stacks of Flapjacks

/*20140917 hanting*/
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    string s;
    while(getline(cin,s))
    {
        stringstream sin(s);
        vector<int> a;
        int num;
        while(sin>>num)
            a.push_back(num);
        int flip[a.size()];
        for(int i=0;i<a.size();i++)
        {
            if(i!=0) cout<<" ";
            cout<<a[i];
            flip[i]=a.size()-i;
        }
        cout<<endl;
        int test_sort=1;
        int largest;
        for(int i=a.size()-1;i>=0 && test_sort;i--)
        {
            test_sort=0;
            largest=i;
            for(int j=0;j<i;j++)//find the largest number
            {
                if(a[j]>a[largest])
                {
                    largest=j;
                }
            }
            if(largest!=i)
            {
                if(largest!=0)//take it to the first
                {
                    cout<<flip[largest]<<" ";
                    reverse(a.begin(),a.begin()+largest+1);
                }
                cout<<flip[i]<<" ";
                reverse(a.begin(),a.begin()+i+1);//and then reverse to i
            }
            for(int j=0;j<a.size()-1;j++)
            {
                if(a[j]>a[j+1])
                {
                    test_sort=1;
                    break;
                }
            }
        }
        cout<<0<<endl;
    }
    return 0;
}

[UVA] 10037 - Bridge

/*20140912 hanting*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    cin>>N;
    int blankline=0;
    while(N--)
    {
        if(blankline) cout<<endl;
        int people;
        cin>>people;
        int temp=people;
        vector<int> a(people);
        for(int i=0;i<people;i++)
        {
            cin>>a[i];
        }
        sort(a.begin(),a.end());
        int A,B,C,D;
        A=0;//first
        B=1;//second
        C=people-2;//last second
        D=people-1;//last
        int sum=0;
        while(people)//consider_sum
        {
            if(people==1)
            {
                sum+=a[A];
                people--;
            }
            else if(people==2)
            {
                sum+=a[B];
                people-=2;
            }
            else if(people==3)
            {
                sum+=a[B]+a[A]+a[D];
                people-=3;
            }
            else
            {
                if(a[B]-a[A]>a[C]-a[B])
                {
                    sum+=a[C]+a[A]+a[D]+a[A];
                }
                else
                {
                    sum+=a[B]+a[A]+a[D]+a[B];
                }
                people-=2;
                C=people-2;
                D=people-1;
            }
        }
        cout<<sum<<endl;
        people=temp;
        A=0;//first
        B=1;//second
        C=people-2;//last second
        D=people-1;//last
        while(people)//cout_tread
        {
            if(people==1)
            {
                cout<<a[A]<<endl;
                people--;
            }
            else if(people==2)
            {
                cout<<a[A]<<" "<<a[B]<<endl;
                people-=2;
            }
            else if(people==3)
            {
                cout<<a[A]<<" "<<a[B]<<endl;
                cout<<a[A]<<endl;
                cout<<a[A]<<" "<<a[D]<<endl;
                people-=3;
            }
            else
            {
                if(a[B]-a[A]>a[C]-a[B])
                {
                    cout<<a[A]<<" "<<a[C]<<endl;
                    cout<<a[A]<<endl;
                    cout<<a[A]<<" "<<a[D]<<endl;
                    cout<<a[A]<<endl;
                }
                else
                {
                    cout<<a[A]<<" "<<a[B]<<endl;
                    cout<<a[A]<<endl;
                    cout<<a[C]<<" "<<a[D]<<endl;
                    cout<<a[B]<<endl;
                }
                people-=2;
                C=people-2;
                D=people-1;
            }
        }
        blankline=1;
    }
    return 0;
}

------------------------------

/* 20151030
 * hanting
 * UVa 10037 - Bridge
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm> //sort
using namespace std;
int solve(int *num, int n);//return sum
vector<pair<int,int> > Go;
vector<int> Back;
int main()
{
    int testCase;
    cin >> testCase;
    while(testCase--)
    {
        Go.clear();
        Back.clear();
        int numN;
        cin >> numN;
        int num[numN];
        for(int i = 0; i < numN; i++)
        {
            cin >> num[i];
        }
        if(numN == 1)
        {
            cout << num[0] << endl;
            cout << num[0] << endl;
        }
        else
        {
            sort(num, num+numN);
            int sum = solve(num, numN);
            cout << sum << endl;
            cout << Go[0].first << " " << Go[0].second << endl;
            for(int i = 1; i < Go.size(); i++)
            {
                cout << Back[i-1] << endl;
                cout << Go[i].first << " " << Go[i].second << endl;
            }
        }
        if(testCase) cout << endl;
    }
    return 0;
}
int solve(int *num, int n)
{
    int sum = 0;
    int i;
    for(i = n-1; i > 2; i-=2)
    {
        int method1 = num[i] + num[0] + num[i-1] + num[0];
        int method2 = num[1] + num[0] + num[i] + num[1];
        if(method1 < method2)
        {
            Go.push_back(pair<int,int>(num[0],num[i]));
            Back.push_back(num[0]);
            Go.push_back(pair<int,int>(num[0],num[i-1]));
            Back.push_back(num[0]);
            sum += method1;
        }
        else
        {
            Go.push_back(pair<int,int>(num[0],num[1]));
            Back.push_back(num[0]);
            Go.push_back(pair<int,int>(num[i-1],num[i]));
            Back.push_back(num[1]);
            sum += method2;
        }
    }
    if(i == 1)
    {
        Go.push_back(pair<int,int>(num[0],num[1]));
        sum += num[1];
    }
    else
    {
        Go.push_back(pair<int,int>(num[0],num[1]));
        Back.push_back(num[0]);
        Go.push_back(pair<int,int>(num[0],num[2]));
        sum += num[1] + num[0] + num[2];
    }
    return sum;
}