两个数组的差值累加和转线段问题
今天这两题都是从Codeforces上扒的,主要是因为也算是一种题型吧
D. Absolute Beauty
思路:这题的思路我只能说还是比较巧妙的,这题也是看了题解才知道该怎么去做
我们可以将ai和bi作为一个线段的两个端点,我们此时来考虑两个线段之间的三种情况
1.两个线段没有交集
我们考虑同向线段,a1<b1&&a2<b2;
那么交换线段后的增加值就是两个线段之间的间隔的二倍
我们来考虑异向线段,a1<b1&&a2>b2
那么交换线段后的增加值还是两个线段之间的间隔的二倍
2.假如线段有一段交集,但是并不会发生一个线段包含另一个线段
不论是同向线段还是异向线段,交换都没有任何值的改变
3假设一个线段包含另一个线段
不论是同向线段还是异向线段,交换都没有任何值的改变
因此,我们只需要让两个直线之间的间隔最大就可以找到最大的值,那么,当a[i]>b[i]的时候,直接交换a[i]和b[i]的值
然后对a数组和b数组进行排序,找到最大的a数组的值减去b数组的最小的值,是否是一个正数,如果是正数,那么就可以在原来线段的基础上,加上两倍的这个数
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];
int b[200005];
void solve()
{cin>>n;int ans=0;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];if(b[i]<a[i])swap(b[i],a[i]);ans+=b[i]-a[i];}sort(a+1,a+1+n);sort(b+1,b+1+n);cout<<ans+max(0LL,2*(a[n]-b[1]))<<"\n";
}signed main()
{cin>>t;while(t--)solve();return 0;
}
F. Swapping Problem
题意:让你求交换一次后的最小值是多少
我们还是进行上述的分析
1.两个线段没有交集
不论是同向线段还是异向线段,交换都没有任何值的改变
2.假如线段有一段交集,但是并不会发生一个线段包含另一个线段
同向线段,交换都没有任何值的改变
异向线段,交换后减少2倍的区间交集
3假设一个线段包含另一个线段
同向线段,交换都没有任何值的改变
异向线段,交换后减少2倍的区间交集
那么我们的思路就很明确了,找到最大的重叠区间,但是时间复杂度为O(n^2),很明显是不对的
那么我们要考虑别的方法了,我们可以首先现将区间按照右区间的大小进行升序排序,然后我们从大到小区枚举每个区间,在枚举区间的时候,我们同时去记录同向线段左端点最小值和异向线段左端点最小值,找到最大的重叠部分即可
#include<bits/stdc++.h>
using namespace std;
#define int long longint t;
int n,k;
int a[200005];
int b[200005];
int f[2];
struct node{int a;int b;int t;
}q[200005];bool cmp(node x,node y)
{return x.b<y.b;
}void solve()
{int ans=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];if(a[i]>b[i]){q[i].t=1;swap(a[i],b[i]);}q[i].a=a[i];q[i].b=b[i];ans+=b[i]-a[i];}sort(q+1,q+1+n,cmp);int len=0;f[0]=0x3f3f3f3f,f[1]=0x3f3f3f3f;//表示正向线段左端点最小,异向线段左端点最小 for(int i=n;i>=1;i--){int flag=q[i].t;if(f[flag^1]<q[i].b){len=max(len,q[i].b-max(q[i].a,f[flag^1]));}f[flag]=min(f[flag],q[i].a);}cout<<ans-2*len;
}signed main()
{t=1;while(t--)solve();return 0;
}