2020百度之星初赛一 Matrix

本文主要是介绍2020百度之星初赛一 Matrix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
有一个二维平面，给定 length[1],length[2],length[3],length[4]，画出 4 个正方形区域。

第 i 个区域为 (x,y) | |x|<=length[i],|y|<=length[i]。

对于一个整点 (x,y) 其权值为 (|x|+|y|)∗cnt，其中 cnt 为覆盖该点的区域个数。（点在区域边界上或者在区域内，都称为被区域覆盖）。

现在需要在至少被一个区域覆盖的整点点集中，选出 k 个两两不同的点，使得总权值和最小。

输出最小的权值总和。

Input
第一行一个整数 T(T≤100) 表示 T 组测试数据。

每组数据有 5 个数字，分别表示 length[1],length[2],length[3],length[4],k。满足 1≤length[1]<length[2]<length[3]<length[4]≤109,0≤k≤1010。

数据保证一定能选出 k 个点。

Output
对每组数据输出一行，表示答案。

Sample Input
4
1 2 3 4 1
1 2 3 4 2
1 2 3 4 6
1 5 7 9 12

Sample Output
0
4
20
64

样例解释
对于第一组样例，取 (0,0)；
对于第二组样例，取 (0,0)、(0,1)；
对于第三组样例，取 (0,0)、(0,1)、(1,0)、(-1,0)、(0,-1)、(1,0)、(4,0)；

参考题解：https://www.cnblogs.com/jianjinxiani/p/13361465.html

思路：
正解里写的是二分最后点的最大权值，表示看得不是很懂。
然后参考了上面题解里的写法。

也就是，枚举当前的权值，然后对于4个区域分别判断对于权值$w$的点，这个区域有多少个点。

因为枚举权值均摊下来，每次可以消去$4\ast \frac{len[1]+len[2]+len[3]+len[4]}{4}$个点。所以$\sqrt{k}$的时间复杂度可以解决这个问题。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
int a[10];ll get(ll x,int len) {if(x > len * 2 || len == 0) return 0;if(x == 0) return 1;if(x <= len) return x * 4;return (2 * len - x + 1) * 4;
}int main() {int T;scanf("%d",&T);while(T--) {ll k;scanf("%d%d%d%d%lld",&a[4],&a[3],&a[2],&a[1],&k);ll ans = 0;ll w = 0;while(k) {for(int i = 1;i <= 4;i++) {if(w % i == 0) {ll num = get(w / i,a[i]) - get(w / i,a[i + 1]);ans += min(k,num) * w;k -= min(k,num);}}w++;}printf("%lld\n",ans);}return 0;
}

这篇关于2020百度之星初赛一 Matrix的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---