简化题目
有一些左端点,右端点和权重,总价值是区间的长度乘上权重(区间长度=右端点-左端点),求最小总价值
开始思考
事实1.所有区间长度加起来是个定值
开始思考:能不能贪心做?答案是能。
在贪心的情况下,交换任意两个区间的端点或权重都会使总价值上升。(可以简化到只有n=2的情况考虑)
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll c[100005]={0},dis[100005]={0};
struct unit
{
int pos;
int id;
}edge[200005];
bool cmp(unit a,unit b)
{
return a.pos<b.pos;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
int len=0;
for(int i=1;i<=n;i++)
{
cin>>edge[i].pos;
edge[i].id=1;
}
for(int i=1+n;i<=2*n;i++)
{
cin>>edge[i].pos;
edge[i].id=2;
}
sort(edge+1,edge+1+2*n,cmp);
for(int i=1;i<=n;i++)cin>>c[i];
sort(c+1,c+n+1);
stack<int> q;
for(int i=1;i<=2*n;i++)
{
if(edge[i].id==2)
{
dis[++len]=edge[i].pos-q.top();
q.pop();
}
else q.push(edge[i].pos);
}
sort(dis+1,dis+n+1);
ll ans=0;
for(int i=1;i<=n;i++)ans+=dis[i]*c[n-i+1];
cout<<ans<<endl;
}
return 0;
}