哪有app制作公司,上海seo排名,网页设计学习心得,怎样在微信上做网站题目
如果此题数据要小一点#xff0c;那么我们可以用克鲁斯卡尔算法通过#xff0c;但是这个数据太大了#xff0c;空间会爆炸#xff0c;时间也会爆炸。
我们发现#xff0c;如果用 MST 做#xff0c;那么很多边的边权都一样#xff0c;我们可以整行整列地删除。
我…题目
如果此题数据要小一点那么我们可以用克鲁斯卡尔算法通过但是这个数据太大了空间会爆炸时间也会爆炸。
我们发现如果用 MST 做那么很多边的边权都一样我们可以整行整列地删除。
我们造一个样例解析一下
------
| | | |
------
| | | |
| | | |
------首先我们删除第一列的栅栏
------
| | | |-----
| | | |
| | | |
------此时答案是 1 1 1。
再删除第一排的栅栏:
------
| |-----
| | | |
| | | |
------此时答案是 3 3 3。
我们继续删除第二列的栅栏
------
| |---
| | | |
| | | |
------此时答案是 5 5 5。
我们继续删除第二行的栅栏
------
| |---
| |
| |
------此时答案是 9 9 9。
我们把第三列的栅栏删除由于之前删除的两行栅栏导致第三列栅栏少删除一个不用删除。
你可以继续造更大的数据发现规律
我们先把每一列每一行的栅栏长度算出来从小到达排序然后用双指针算法两个指针 i i i 和 j j j第一个记录统计到哪一行第二个记录统计到哪一列这两个变量的初始值应该为 2 2 2然后把第一列第一行栅栏删除。讨论时如果我们当前讨论的行比列要短就删除 m − j 1 m-j1 m−j1 个栅栏因为之前删除的栅栏导致我们现在不用删除一些栅栏。反之同理就是 n − i 1 n-i1 n−i1 个栅栏。如果一个指针走完了那么所有的都是联通的就不用再循环了。时间复杂度 O ( n ) O(n) O(n)通过。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
int h, w, n, m;
int a[300000], b[300000];
long long a1[300000], b1[300000];
long long ans;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin h w n m;for (int i 1; i n; i ) cin a[i];for (int i 1; i m; i ) cin b[i];sort(a 1, a n 1);sort(b 1, b m 1);n;a[n] h;m;b[m] w;for (int i 1; i n; i ) {a1[i] a[i] - a[i - 1];}for (int i 1; i m; i ) {b1[i] b[i] - b[i - 1];}sort(a1 1, a1 n 1);sort(b1 1, b1 m 1);
// for (int i 1; i n; i ) {
// cout a1[i] ;
// }
// cout \n;
// for (int j 1; j m; j ) {
// cout b1[j] ;
// }
// cout \n;int i 2, j 2;ans a1[1] * (m - 1);ans b1[1] * (n - 1);while (i n j m) {if (a1[i] b1[j]) {ans a1[i] * (m - j 1);i;}else {ans b1[j] * (n - i 1);j;}}cout ans;return 0;
}
