本次考试有两道编程题目。
题目描述(1)
给定一个数组A和一个数k，求A的子数组的和是k的倍数的最长子串的长度。数组A的长度和k可能很大！
分析
由于数组A的长度和k可能很大，因此如果使用朴素解法一定会遇到数值溢出和超时问题。
解决数值溢出问题： 假设子数组的和是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）小刘老师想让学生互相改试卷以节省自己的时间。小刘老师的策略是将学生分为n个组，每个组有si个学生，小刘老师先讲一个组的试卷收集起来放在桌子上，然后小刘老师访问下一个组，如果下一个组的学生有x个人，就从桌子上放，拿x个试卷放，随机发放给当前访问的组的学生，然后将这组学生的自己的试卷收集起来放到桌子的底部。但小刘老师可能会遇到，(1)访问当前组的时候，桌子上的试卷数目小于当前组的人数的情况，(2)又不想让学生改到自己的试卷。问给定一个分组，小刘老师是否能找到满足条件的访问顺序。
如果人数最大的一组人数和max 大于 总人数1/2, 则不可能找到满足条件(1)、(2)的访问顺序。
按从大到小排的话，如果第一组的人数小于等于剩下所有组的人数总和就一定不会改到自己的试卷，从大到小排的话只需考虑第一个组会不会改到自己的就行了。
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();
