京东8.24笔试第三批-后端开发（AK）

1.基础选择题10题

2.java八股选择题5题（可以选c++/go）

3.编程题3题

（1）给定一个10^100的数 n，问0~n有多少个能被100整除的数

做法：string读入后两位不输出

（2）有一个n * m矩阵，初始全为白色，t次操作，每次操作为修改其中一个颜色为黑色，或者询问某个坐标的上下左右第一个为白色的坐标。

做法： 数据范围 1<= n, m <= 100, 1 <= t <= 1e5， 直接模拟就好了。

(3) 给定 n 个数字，找到一个长度最大的区间，使得区间内所有数任取三个都能组成三角形

数据范围：1 <= n <= 1e6

做法： 首先不难想到对于判断一个区间是否满足条件，只需要看该区间的【最大值，次大值，最小值】以及【最大值，次小值，最小值】是否能组成三角形，这两个条件满足则 整个区间满足。

剩下的就是双指针跑一遍就行了，难点在于维护【最大值，次大值，次小值， 最小值】，这里用的是multiset，调了好久才960ms卡过去，差点就上手动快读了

代码：

#include <iostream>
#include <set>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], ans, l, r;
int zd, cd, zx, cx;
multiset<int> se;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	int nl = 1, nr = 1;
	while(nr < n) {
		se.insert(a[nr]);
		if(se.size() > 2) {
			zd = *se.rbegin();
			cd = *(++ se.rbegin());
			zx = *se.begin();
			cx = *(++ se.begin());
			if(zx + cx > zd && zd - cd < zx) {
				if(nr - nl + 1 > ans) {
					ans = nr - nl + 1;
					l = nl;
					r = nr;
				}
			}
			else {
				auto it = se.find(a[nl]);
				se.erase(it);
				nl ++;
			}
		}
		nr ++;
	}
	if(ans > 2) 
		cout << l << ' ' << r << '\n';
	else 
		cout << "1 2\n" << endl;
}