本次考試有兩道編程題目。
題目描述(1)
給定一個(gè)數(shù)組A和一個(gè)數(shù)k昵观，求A的子數(shù)組的和是k的倍數(shù)的最長(zhǎng)子串的長(zhǎng)度晾腔。數(shù)組A的長(zhǎng)度和k可能很大！
分析
由于數(shù)組A的長(zhǎng)度和k可能很大啊犬，因此如果使用樸素解法一定會(huì)遇到數(shù)值溢出和超時(shí)問(wèn)題灼擂。
解決數(shù)值溢出問(wèn)題： 假設(shè)子數(shù)組的和是tsum, 如果tsum可以整除k，那么tsum % k 等價(jià) (ary[i] % k + ... + ary[j]%k) %k (其中tsum == ary[i]+...+ary[j])
解決超時(shí)問(wèn)題： 策略：緩存椒惨，夾逼搜索
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）小劉老師想讓學(xué)生互相改試卷以節(jié)省自己的時(shí)間。小劉老師的策略是將學(xué)生分為n個(gè)組康谆，每個(gè)組有si個(gè)學(xué)生领斥，小劉老師先講一個(gè)組的試卷收集起來(lái)放在桌子上，然后小劉老師訪問(wèn)下一個(gè)組沃暗，如果下一個(gè)組的學(xué)生有x個(gè)人月洛，就從桌子上放，拿x個(gè)試卷放孽锥，隨機(jī)發(fā)放給當(dāng)前訪問(wèn)的組的學(xué)生嚼黔，然后將這組學(xué)生的自己的試卷收集起來(lái)放到桌子的底部细层。但小劉老師可能會(huì)遇到，(1)訪問(wèn)當(dāng)前組的時(shí)候唬涧，桌子上的試卷數(shù)目小于當(dāng)前組的人數(shù)的情況疫赎，(2)又不想讓學(xué)生改到自己的試卷。問(wèn)給定一個(gè)分組碎节，小劉老師是否能找到滿足條件的訪問(wèn)順序捧搞。
如果人數(shù)最大的一組人數(shù)和max 大于 總?cè)藬?shù)1/2, 則不可能找到滿足條件(1)、(2)的訪問(wèn)順序狮荔。
按從大到小排的話胎撇，如果第一組的人數(shù)小于等于剩下所有組的人數(shù)總和就一定不會(huì)改到自己的試卷，從大到小排的話只需考慮第一個(gè)組會(huì)不會(huì)改到自己的就行了殖氏。
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();
