本次考試有兩道編程題目。

題目描述(1)

給定一個數(shù)組A和一個數(shù)k，求A的子數(shù)組的和是k的倍數(shù)的最長子串的長度。數(shù)組A的長度和k可能很大！

分析

由于數(shù)組A的長度和k可能很大，因此如果使用樸素解法一定會遇到數(shù)值溢出和超時問題。
解決數(shù)值溢出問題： 假設子數(shù)組的和是tsum, 如果tsum可以整除k，那么tsum % k 等價 (ary[i] % k + ... + ary[j]%k) %k (其中tsum == ary[i]+...+ary[j])

解決超時問題： 策略：緩存，夾逼搜索

const int maxn = 1e5 + 10;
int ary[maxn];
int n;
int ans=0;

int solver(int ary[]){

    int ans =0;
    long long sum[maxn];
    sum[0]=ary[0];
    for(int i=1; i<=n; i++){
        sum[i] = sum[i-1] + ary[i];
    }
    int i,j;
    for(i=1; i<=n; ++i){
        for(j=n; j>=i; j--){
            if((sum[j]-sum[i]) % k==0){
                if(ans < j-i+1)
                    ans = j-i+1;
                break;
            }
        }
        if(j != (i-1)) break;
        if(ans!=0) break;
    }
    return ans;
}

下列算法，主要利用：
x=sum[j] % k
x=sum[i] % k
x 可以不是 0
則 (sum[j] - sum[i]) % k == 0

const int maxn = 1e5 + 10;
int ary[maxn];
int n;
int idxs[maxn]; // idxs[ sum % k] = i;
int ans=0;

    cin >> n;
    idxs[0] = ary[0] = 0;
    for(int i=1; i<n; ++i) {
            cin >> ary[i];
    }
    cin >>k;
    for(int i=1; i<=n; ++i) {
            ary[i] = (ary[i] + ary[i-1])%k;
    }
    for(int i=1; i<=k; ++i) idxs[i] = maxn*2;
    ans = 0;
    for(int i=1; i<=n; ++i){
        ans = max(ans, i-idxs[ary[i]%k); //
        idxs[ary[i] % k] = min(idxs[ary[i]%k], i);
    }
    cout << ans << endl;;

題目描述(2)

（2）小劉老師想讓學生互相改試卷以節(jié)省自己的時間。小劉老師的策略是將學生分為n個組，每個組有s_i個學生，小劉老師先講一個組的試卷收集起來放在桌子上，然后小劉老師訪問下一個組，如果下一個組的學生有x個人，就從桌子上放，拿x個試卷放，隨機發(fā)放給當前訪問的組的學生，然后將這組學生的自己的試卷收集起來放到桌子的底部。但小劉老師可能會遇到，(1)訪問當前組的時候，桌子上的試卷數(shù)目小于當前組的人數(shù)的情況，(2)又不想讓學生改到自己的試卷。問給定一個分組，小劉老師是否能找到滿足條件的訪問順序。

如果人數(shù)最大的一組人數(shù)和max 大于 總?cè)藬?shù)1/2, 則不可能找到滿足條件(1)、(2)的訪問順序。

按從大到小排的話，如果第一組的人數(shù)小于等于剩下所有組的人數(shù)總和就一定不會改到自己的試卷，從大到小排的話只需考慮第一個組會不會改到自己的就行了。

        Scanner rd = new Scanner(System.in);
        
        while(rd.hasNext()) {
            int n = rd.nextInt();
            int[] ary = new int[n];

            long sum = 0;
            long max = -1;
            for(int i=0; i<n; ++i) {
                ary[i] = rd.nextInt();
                sum += ary[i];
                max = max < ary[i] ? ary[i] : max;
            }
            //Arrays.sort(ary);
            if( sum - max*2 <0) {
                System.out.println("No");
            }else {
                System.out.println("Yes");
            }
        }
        
        rd.close();