大神的世界

想法 1. 

將數列小到大排序, 再 linear scan 出 duplicate 和 missing

時間複雜度 O(nlogn)

想法 2.

假設 duplicate 為 a, missing 為 b , 則

d1 = 理想數列和 - 實際數列和  =  a - b     (理想數列和代表原本的等差數列)

d2 = 理想數列平方和 - 實際數列平方和  =  a^2 - b^2 = (a + b)(a-b)

=>

a = (d1 + d2/d1) / 2

b = a - d1

時間複雜度 O(n)

(我用方法二，但還是要 9 ms , 應該是我寫太爛了 ......)

#include <iostream>
#include <cstdio>
#include <sstream>

using namespace std;

#define INFINITE   2147483647

int main()
{
    int times;
    long long int actualSum, idealSum, actualSqrSum, idealSqrSum, termNum, missing, duplicate, tmp;
    int d, min, max;
    int num[1000];

    string str;

    while(cin >> times){
        
        getchar();

        while(times--){
            getline(cin, str);
            stringstream ss;
            ss.clear();
            ss << str;

            termNum = actualSum = idealSum = actualSqrSum = idealSqrSum = 0;
            max = -INFINITE;
            min = INFINITE;

            while(ss >> tmp){
                num[termNum++] = tmp;
                
                if(tmp < min)
                    min = tmp;

                if(tmp > max)
                    max = tmp;

                actualSum += tmp;
                actualSqrSum += tmp*tmp;
            } 

            d = (max - min)/(termNum-1);
            idealSum = (min+max)*termNum/2;

            tmp = min;
            for(int i = 0; i<termNum; tmp+=d, i++){
              idealSqrSum += tmp*tmp;
            }

            long long int d1 = actualSum - idealSum;
            long long int d2 = actualSqrSum - idealSqrSum;

            duplicate = (d1 + d2/d1)/2;
            missing = duplicate - d1;

            cout << missing << " " << duplicate << endl;
        }
    }
    return 0;
}