「高效算法設計」

UVA11078 Open Credit System

大緻題意

給一個長度為n的整數序列a0 a1 a2….an-1,找出兩個整數ai和aj（i < j） 使得ai-aj最大 輸入

第一行 組數 T 每組資料 第一行輸入資料數量n(2<=n<=1e+5) 接下來是n個不超過150000的整數 輸出

對于每組資料，輸出最大ai-aj。

題目價值;

• 學會找到題目解答的關鍵。
• 本題n^2解法是兩個for循環，然後逐個比較答案。但是仔細分析題目會發現：題目要求的隻是j之前的一個最大值。是以題目關鍵是a[j]之前的最大值，是以隻要每次與更新最大值maxn就好了，優化為o（n）。

UVA11549 Calculator Conundrum

題意：把k反複平方，隻留前n位，求在乘的過程中的max。

題目價值

• 發現題目特性：平方後截斷的數有循環性。
• 引入floyd判圈法：
• 如果是循環出現，或者環狀資料結構。兩個人從相同的起點，最終會相遇。
• -

詳情點這裡

UVA1121 Subsequence

題意：n個正整數組成的序列，求最短的字串和為s

• 樸素算法 n^3枚舉開頭結尾和累加
• 字首數組優化為n^2 （TLE）
• 由sum[j] - sum[i-1] >= s =>sum[i-1] <=sum[i] - s; 是以隻枚舉j，因為sum數組單調遞增，是以用二分查找找i。nlogn（AC）
• 因為sum單調，i也單調。優化為n。

code1

o（n^2)

#include<bits/stdc++.h>
using namespace std;
#define N 100000 + 10
int a[N],n,s;
int sum[N];
int main() {
    while (scanf("%d%d",&n,&s) == ) {
        for (int i = ; i<= n ;i++) {
            scanf("%d",&a[i]);
            sum[i] = a[i] + sum[i-];
        }
        int ans = N*1000;
        for (int i = ;i <=n;i++)
        for(int j = i + ;j <=n ;j++)
        {
         if(sum[j] - sum[i - ] >= s)ans = min (ans,j - i + );
        }
        printf("%d\n",ans == N*1000?  : ans);
    }
    return ;
}
           

code2

o（nlogn）

int ans = N*;
        for(int j = ;j <=n ;j++)
        {
            int i = lower_bound(sum,sum + j,sum[j] - s) - sum;
         if(i > )ans = min (ans,j - i + );
        }
           

code3

o（n）

for(int j = ;j <=n ;j++)
        {
            if(sum[i-] > sum[j] - s)continue;
            while(sum[i] <= sum[j] - s)i++;
            ans = min(ans,j - i + );
        }
           

UVA10755 Garbage Heap

大意：A×B×C的長方體，價值以（1，1，1）（1，1，2）…(1,1,C)..(1,2,1)..(1,2,C)給出。求價值最大的子立方體;

關鍵詞 ： 降維，字首和。

題目價值

• 解決高維問題一般方法是降維再推廣到多元上來。
• 題目基礎是最大連續字段和，此處拓展到3維。
• 題目求解分為兩部分：
• 一.求字首數組。
• 二.最大連續字段和。