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;
}