A40859. 密文搜索
填空题
困难
知识点
题目描述
密文搜索
题目描述
蓝桥村的居民都生活在一条公路的边上，公路的长度为L，每户家庭的 位置都用这户家庭到公路的起点的距离来计算，第i户家庭距起点的距 的终点。
已知每户家庭都会向着远离公路起点的方向去参加集会，参加集会的路程开销为家庭内的人数ti与距离的乘积。
给定每户家庭的位置di和人数ti，请为村委会寻找最好的集会举办地：p1, p2, p3, p4 (p1<=p2<=p3<=p4=L),使得村内所有人的路程开销和最小。
输入格式
输入的第一行包含两个整数n, L，分别表示蓝桥村的家庭数和公路长度。
接下来n行，每行两个整数di, ti，分别表示第i户家庭距离公路起点的距离和家庭中的人数。
输出格式
输出一行，包含一个整数，表示村内所有人路程的开销和。
样例输入
6 10
1 3
2 2
4 5
5 20
6 5
8 7
样例输出
18
参考答案
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<math.h>
#include<algorithm>
#include<set>
#include<string.h>
#include<string>
#include<map>
#include<queue>
using namespace std;
#define N 100008
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
struct node{
ll dis,num;
}p[N];
ll num[N],d[N];//d[i]表示p[i]到p[i-1]的距离
ll s4[N];
int main(){
int n;
ll L;
scanf("%d%I64d",&n,&L);
int x,y;
num[0]=0ll;
for(int i=1;i<=n;i++){
num[i]=0ll;
scanf("%I64d%I64d",&p[i].dis,&p[i].num);
num[i]=num[i-1]+p[i].num;
if(i==1)d[i]=0;
else d[i]=p[i].dis-p[i-1].dis;
}
p[n+1].dis=L;p[n+1].num=0;
if(n<=3){
printf("0\n");
}
else{
s4[n+1]=0;
for(int i=n;i>=1;i--){//从i点到n+1点所有人需要走到s4的距离
s4[i]=s4[i+1]+ (p[n+1].dis-p[i].dis)*p[i].num;
}
ll ans=(ll)inf*1000;
ll s1=0,s2=0,s3=0;
for(int i=1;i<=n-2;i++){//暴力枚举三个点的位置
s1+= num[i-1]*d[i];
s2=0;
if(s1>=ans)continue;
for(int j=i+1;j<=n-1;j++){
s2+= ( num[j-1]-num[i])*d[j];
s3=0;
if(s1+s2>=ans)continue;
for(int k=j+1;k<=n;k++){
s3+=(num[k-1]-num[j])*d[k];
ll s=s4[k+1];//表示最后一段的结果
if(ans>s1+s2+s3+s){
// printf("%d %d %d %d\n",i,j,k,n+1);输出新区间
ans=s1+s2+s3+s;
}
}
}
}
printf("%I64d\n",ans);
}
return 0;
}
上一题
下一题