AK 微众银行 9.3 笔试 Java后端方向

T1(模拟,二分)

• (没看清买的糖果只有前缀，一开始用二分写了，后来意识到也没改了，简单写的话，直接模拟就好了)

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

const int N = 50010;

int n; int a[N];

bool check(int X) {
	unordered_map<int, int> cnt;
	for(int i = 1; i <= X; i ++) cnt[a[i]] ++ ;

	if(cnt.size() == X) return true;
	return false;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];

	int l = 1, r = n;
	while(l < r) {
		int mid = l + r + 1 >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}

	cout << r << endl;
	return 0;
}

T2(思维,双指针)

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 50010;

int n; int a[N];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	sort(a + 1, a + n + 1);

	ll ans = 0, last = 0; for(int i = 1; i <= n; i ++) {
		int j = i; while(j <= n && a[j] == a[i]) j ++ ;
		int cnt = j - i; bool flag = false;
		if(last >= a[i]) ans += (last + 1 - a[i]) * 1ll * cnt, flag = true;
		ans += (cnt - 1) * 1ll * cnt / 2;
		if(flag) a[i] = last + 1; last = a[i] + cnt - 1; i = j - 1;
	}

	cout << ans << endl;
	return 0;
}

T3(模拟,前缀和)

• 应该是数据出小了，按理不应该能直接过的，算是捡漏了吧 hh

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 100010;

int n, u, v; int a[N]; ll pre[N];

int main() {
	scanf("%d%d%d", &n, &u, &v);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + 0ll + a[i];

	int ans = 0;
	for(int len = v; len <= n; len += v) {
		for(int i = 1; i + len - 1 <= n; i ++) {
			if((pre[i + len - 1] - pre[i - 1]) * 1ll * v == len * 1ll * u) ans ++ ;
		}
	}

	cout << ans << endl;
	return 0;
}