区間オーバーライド問題(欲張りアルゴリズム)

1302 ワード

区間オーバーライド問題
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
x座標軸上の座標が[i−1,i]の長さが1の区間をiで表し、n(1≦n≦200)個の異なる整数を与え、n個のこのような区間を表す.
現在、m本の線分を描いてすべての区間を覆うように要求されています.
条件は、各線分は任意に長くすることができますが、描く線分の長さの和が最小であることです.
また、線分の数はm(1≦m≦50)を超えない.

Input
入力には複数のデータ群が含まれ、各データ群の第1行は区間個数nと所望の線分数mを表し、第2行はn点の座標を表す.
Output
各グループの出力は1行を占め、mセグメントの最小長さと出力されます.
Sample Input

5 3
1 3 8 5 11

Sample Output

Hint
注意:テーマデータは2018.4.16更新
Source

基本的な考え方:まず、入力したデータを並べ替えて、それから1つの配列bで間の隙間を格納します.
次にb配列を並べ替えます.欲張りな考え:まず間隔のない直線(つまり1本の直線の場合)と見なし、2本の直線の場合、最大の隙間を1つ減らし、3本の場合に最大の隙間を2つ減らす必要があります.
同理n個の直線の場合、n-1個のギャップを減算する必要があります.
コードは次のとおりです.

#include
#include
#include

void q_sort(int *a , int left , int right)//    
{
    int i , j , key ;
    if(left>=right)
        return ;
    i = left ;
    j = right ;
    key = a[i] ;
    while(i=key)
            j-- ;
        a[i] = a[j] ;
        while(i

プログラマーの進級のアルゴリズムの練習:LeetCodeの特別な場

makefileコンパイルファイルの紹介