猫史档案馆

急_开_锁_办_证810864

天梯排行：

#include <iostream>

int main(){
	int qsize; //数据规模
	int lastNum = -1, lastCnt = 0， currNum; //上一个处理的级别编号、上一个级别编号的出现次数、当前处理的级别编号
	int maxNum, maxCnt = 0; //记录出现最多的级别编号和对应次数

	cin >> qsize; //读取数据规模

	for(int i = 1; i <= qsize; i++){ //依次读取各个具体的级别编号
		cin >> currNum; //每次读取1个数

		if(currNum != lastNum){ //如果发现正在处理的是1个新级别编号
			//检查是否需要更新最大数量记录
			if(lastCnt > maxCnt){ //如果上一个编号的出现次数超过了最大已知值
				maxCnt = lastCnt;
				maxNum = lastNum;
			}

			//用当前的信息及时更新上一个信息
			lastNum = currNum;
			lastCnt = 1; //当前的计数值变为1
		}else{ //如果发现正在处理的是1个旧级别编号
			lastCnt++; //直接让当前的计数值递增
		}
	}

	//结束数据输入的循环后，还需要检查一次是否需要更新最大数量记录，保证最后1个级别编号也参与次数比较
	if(lastCnt > maxCnt){ //如果上一个编号的出现次数超过了最大已知值
		maxCnt = lastCnt;
		maxNum = lastNum;
	}

	cout << maxNum; //输出结果

	return 0;
}

天梯排行变形问题：

#include <iostream>

int main(){
	int qsize, qpos; //数据规模、最后所问级别编号的位置
	int nums[1001], cnts[1001]; //记录各个不同的级别编号和对应次数
	int lastIdx = 0, currNum; //上一个处理的级别编号的索引、当前新输入的级别编号

	cin >> qsize; //读取数据规模

	nums[lastIdx] = -0x3f; //先将第一个编号取为一个数据中不会出现的很大的负数
	for(int i = 1; i <= qsize; i++){ //依次读取各个具体的级别编号
		cin >> currNum; //每次读取1个数

		if(currNum != nums[lastIdx]){ //如果发现正在处理的是1个新级别编号
			//用当前的信息及时更新上一个信息
			lastIdx++;
			nums[lastIdx] = currNum;
			cnts[lastIdx] = 1; //当前的计数值变为1
		}else{ //如果发现正在处理的是1个旧级别编号
			cnts[lastIdx]++; //直接让当前的计数值递增
		}
	}

	cin >> qpos;
	for(int i = 1; i <= lastIdx; i++){ //有效编号从0开始
		qpos -= cnts[i]; //每次向后数若干个相同的数，即将位置序号减去前几个数的出现次数
		if(qpos <= 0){ //如果位置的值一直减到了0
			cout << cnts[i]; //输出结果
            break; //不必继续循环
		}
	}

	return 0;
}

最大子段和（分治）：

#include <iostream>
using namespace std;

int arr[1000];

int findAns(int beginPos, int endPos){ //注意只取左端点，不取右端点
	if(endPos - beginPos <= 1){ //如果左右两侧间距太小
		return arr[beginPos];
	}

	int midPos = (beginPos + endPos) / 2; //计算中点位置

	int leftVal = findAns(beginPos, midPos); //只向左递归查找
	int rightVal = findAns(midPos, endPos); //只向右递归查找

	int maxVal = leftVal > rightVal ? leftVal : rightVal; //当前已知的最大值

	//查找横跨左右两侧的区间
	for(int i = beginPos; i < midPos; i++){ //确定子区间的可能左端点
		for(int j = midPos; j <= endPos; j++){ //确定子区间的可能右端点
			if(i == beginPos && j == endPos){ //最后再单独考虑整个区间的情形，避免无限递归
				continue;
			}

			int spanVal = findAns(i, j); //递归查找
			if(spanVal > maxVal){ //如果可以更新最大值
				maxVal = spanVal;
			}
		}
	}

	//单独处理整个区间本身的情况
	int wholeVal = 0;
	for(int i = beginPos; i < endPos; i++){
		wholeVal += arr[i];
	}
	if(wholeVal > maxVal){ //如果可以更新最大值
		maxVal = wholeVal;
	}

	return maxVal;
}

int main(){
	int qsize; //问题规模

	cin >> qsize;
	for(int i = 1; i <= qsize; i++){
		cin >> arr[i]; //依次读取各个具体值
	}

	cout << findAns(1, qsize + 1); //在索引范围[1, qsize + 1)内查找并输出结果

	return 0;
}

点赞就不必了。话说今天教师节，你可以考虑给你们老师冲点Q币，让他们周末打游戏练级也爽一爽惹。

点赞1