五連擊數組

前言
每天必須看道算法題目才能安心啊，畢竟是快到9月份找工作的關鍵時刻了。最近忙得快跪了，一周下來到周五眼睛必然是極度充血的狀態，沒辦法，需要學習和復習的東西太多，加上還有項目上的任務，羅列幾個主要的任務：
看完劍指offer，7月14日前必須完成
邊做准信項目邊學習redis源碼，項目在7月21日前必須將服務器端代碼完成
學習php內核一些知識，這個看時間情況吧
信息檢索，兼顧論文，估計7月14到7月21日我需要拿出一周來突擊論文，請假就好了
一直以來工作上最深的感觸就是孤獨，中科院的一哥們跟我感覺類似，我發現自己也是個人才，有非常好的忍耐力和意志力，特別能堅持，到了研究生這個階段，之所以能拉開差距關鍵就是你是否堅持了你想學習的東西和做人的准則（ps：天才除外）

題目
[html]  題目描述： 
在任意一個數組當中，若你能找出有五個及五個以上的連續元素時，我們就稱它為五連擊數組。但是這種數組並不是時常會有，你的任務就是通過增加最少的元素，使一個數組成為一個五連擊數組。 
輸入： 
每個測試文件包含多個測試案例，每個測試案例包括兩行。 
第一行代表輸入數組的元素個數N，其中0 < N <= 1000。 
第二行則包含有N個非負整數，代表數組的元素。 
輸出： 
對於每一個測試案例輸出一行，代表最少需要添加的元素數，使得數組成為一個五連擊數組。 
樣例輸入： 
3 
1 3 4 
1 
1 
樣例輸出： 
2 
4 

題目描述：
在任意一個數組當中，若你能找出有五個及五個以上的連續元素時，我們就稱它為五連擊數組。但是這種數組並不是時常會有，你的任務就是通過增加最少的元素，使一個數組成為一個五連擊數組。
輸入：
每個測試文件包含多個測試案例，每個測試案例包括兩行。
第一行代表輸入數組的元素個數N，其中0 < N <= 1000。
第二行則包含有N個非負整數，代表數組的元素。
輸出：
對於每一個測試案例輸出一行，代表最少需要添加的元素數，使得數組成為一個五連擊數組。
樣例輸入：
3
1 3 4
1
1
樣例輸出：
2
4

思路
一個三星很水的題目，因為有負數的存在，不方便直接用hash數組實現，所以可以考慮：
快速排序
依次遍歷每個數，記錄最小能實現num+4的值，輸出即可
自己模擬了一下快排，當作算法回顧了

AC代碼
 

 #include <stdio.h>   
#include <stdlib.h>   
   
int pivot_partition(int *arr, int left, int right);  
void quick_sort(int *arr, int begin, int end);  
int in_array(int *arr, int n, int data);  
   
int main(void)  
{  
    int i, j, min, count, n, *arr;  
   
    while (scanf("%d", &n) != EOF) {  
        arr = (int *)malloc(sizeof(int) * n);  
        for (i = 0; i < n; i ++)  
            scanf("%d", arr + i);  
   
        quick_sort(arr, 0, n - 1);  
   
        /* 測試 
        for (i = 0; i < n; i ++) 
            printf("%d ", arr[i]); 
        printf("\n"); 
        */  
   
        for (i = 0; i < n; i ++) {  
            for (j = arr[i], count = 0; j <= arr[i] + 4; j ++) {  
                if (in_array(arr, n, j))  
                    continue;  
                else  
                    count ++;  
            }  
            if (i == 0) {  
                min = count;  
            } else {  
                min = (min < count) ? min : count;  
            }  
        }  
   
        printf("%d\n", min);  
        free(arr);  
    }  
   
    return 0;  
}  
   
int in_array(int *arr, int n, int data)  
{  
    int i, flag = 0;  
   
    for (i = 0; i < n; i ++) {  
        if (arr[i] == data) {  
            flag = 1;  
            break;  
        }  
    }  
   
    return flag;  
}  
   
void quick_sort(int *arr, int begin, int end)  
{  
    int pivot;  
   
    if (begin < end) {  
        pivot = pivot_partition(arr, begin, end);  
        quick_sort(arr, begin, pivot - 1);  
        quick_sort(arr, pivot + 1, end);  
    }  
}  
   
   
int pivot_partition(int *arr, int left, int right)  
{  
    int stand = arr[left];  
   
    while (left < right) {  
        while (left < right && arr[right] >= stand)  
            right --;  
        if (left < right)  
            arr[left ++] = arr[right];  
           
        while (left < right && arr[left] <= stand)  
            left ++;  
        if (left < right)  
            arr[right --] = arr[left];  
    }  
    arr[left] = stand;  
    return left;  
}  
/************************************************************** 
    Problem: 1394 
    User: wangzhengyi 
    Language: C 
    Result: Accepted 
    Time:0 ms 
    Memory:912 kb 
****************************************************************/  

#include <stdio.h>
#include <stdlib.h>
 
int pivot_partition(int *arr, int left, int right);
void quick_sort(int *arr, int begin, int end);
int in_array(int *arr, int n, int data);
 
int main(void)
{
    int i, j, min, count, n, *arr;
 
    while (scanf("%d", &n) != EOF) {
        arr = (int *)malloc(sizeof(int) * n);
        for (i = 0; i < n; i ++)
            scanf("%d", arr + i);
 
        quick_sort(arr, 0, n - 1);
 
        /* 測試
        for (i = 0; i < n; i ++)
            printf("%d ", arr[i]);
        printf("\n");
        */
 
        for (i = 0; i < n; i ++) {
            for (j = arr[i], count = 0; j <= arr[i] + 4; j ++) {
                if (in_array(arr, n, j))
                    continue;
                else
                    count ++;
            }
            if (i == 0) {
                min = count;
            } else {
                min = (min < count) ? min : count;
            }
        }
 
        printf("%d\n", min);
        free(arr);
    }
 
    return 0;
}
 
int in_array(int *arr, int n, int data)
{
    int i, flag = 0;
 
    for (i = 0; i < n; i ++) {
        if (arr[i] == data) {
            flag = 1;
            break;
        }
    }
 
    return flag;
}
 
void quick_sort(int *arr, int begin, int end)
{
    int pivot;
 
    if (begin < end) {
        pivot = pivot_partition(arr, begin, end);
        quick_sort(arr, begin, pivot - 1);
        quick_sort(arr, pivot + 1, end);
    }
}
 
 
int pivot_partition(int *arr, int left, int right)
{
    int stand = arr[left];
 
    while (left < right) {
        while (left < right && arr[right] >= stand)
            right --;
        if (left < right)
            arr[left ++] = arr[right];
         
        while (left < right && arr[left] <= stand)
            left ++;
        if (left < right)
            arr[right --] = arr[left];
    }
    arr[left] = stand;
    return left;
}
/**************************************************************
    Problem: 1394
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:912 kb
****************************************************************/