两个数组的差值累加和转线段问题

今天这两题都是从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;
}