自己建设个小网站要什么手续,做网站和网页区别,做网站第二年要续费吗,有关图书网站建设策划书题目内容 原题链接 给定长度为 n n n 的数组 a a a 和一个整数 k k k #xff0c;保证 n n n 为偶数。 问将 n n n 个数两两配对#xff0c;得到的值为 ⌊ a i a j k ⌋ \lfloor\frac{a_ia_j}{k}\rfloor ⌊kaiaj⌋
问如何配对使得总和最大#xff0c;最大值是…题目内容 原题链接 给定长度为 n n n 的数组 a a a 和一个整数 k k k 保证 n n n 为偶数。 问将 n n n 个数两两配对得到的值为 ⌊ a i a j k ⌋ \lfloor\frac{a_ia_j}{k}\rfloor ⌊kaiaj⌋
问如何配对使得总和最大最大值是多少
数据范围 1 ≤ n , m ≤ 2 × 1 0 5 1\leq n,m \leq 2\times 10^5 1≤n,m≤2×105 1 ≤ k ≤ 1000 1\leq k\leq 1000 1≤k≤1000 0 ≤ a i ≤ 1 0 9 0\leq a_i \leq 10^9 0≤ai≤109
题解
对于每个数 x x x 来说 ⌊ x k ⌋ \lfloor\frac{x}{k}\rfloor ⌊kx⌋ 是不会变的所以我们先将这部分加上然后 x x x 变为 x m o d k x\bmod k xmodk 。这样存下所有 x m o d k x\bmod k xmodk 的值。
我们继续考虑在 [ 0 , k − 1 ] [0,k-1] [0,k−1] 内的数 x x x 和 y y y 如果 x y ≥ k xy\geq k xy≥k 则会给答案加 1 1 1 因为 x y ≤ 2 k − 2 xy\leq 2k-2 xy≤2k−2 。
此时最小的数必然是考虑和最大的数相加判断是否大于等于 k k k 如果不可以则说明最小的数无法配对凑出一个 ≥ k \geq k ≥k 的。
这部分用双指针实现即可。
时间复杂度 O ( n ) O(n) O(n)
代码
#include bits/stdc.h
using namespace std;typedef long long ll;const int N 200010, M 1000;
int x;
int ok[M];
int temp[N];
void solve() {int n, k;cin n k;memset(ok, 0, k * sizeof(int));ll ans 0;for (int i 0; i n; i) {cin x;ans x / k;ok[x % k] 1;}int t 0;for (int i 1; i k; i) {while (ok[i] 0) temp[t] i, ok[i]--;}for (int i 0, j t - 1; i j; i) {if (temp[i] temp[j] k) {ans 1;j - 1;}}cout ans \n;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin T;while (T--) solve();return 0;
}
