专栏文章
题解：P12725 [KOI 2021 Round 2] 累计距离
P12725题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minjp6vl
- 此快照首次捕获于
- 2025/12/02 03:31 3 个月前
- 此快照最后确认于
- 2025/12/02 03:31 3 个月前
题意简述
数轴上有 个村庄，第 个村庄中有 个村民，每次给定一个数 ，求出所有村民到 的长度总和。
思路1（暴力）
这道题的暴力很好写，只要对于每次询问，去暴力统计总和。
于是我得到了以下代码
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T,XXXXXXXX,sum;
struct ll
{
int x,y;
}a[200010];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>T;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
while(T--)
{
cin>>XXXXXXXX;
sum=0;
for(int i=1;i<=n;i++)//暴力求解
{
sum+=a[i].x*abs(a[i].y-XXXXXXXX);
}
cout<<sum<<"\n";
}
return 0;
}
于是不出意料的超时了
超时思路2（正解）
正解思路还是比较简单的，主要是处理一下绝对值
其实这个绝对值可以理解为这样： 时, 就是 而在 时, 就是 而这时只需要找出第一个大于 的 就行了。
只不过需要注意不能直接枚举，会超时，改为二分差找就可以解决这个问题。
接下来就容易了，需要两个前缀和数组，一个统计人数，一个统计村庄 的和。
于是一份正解代码就出现了
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T,lc,sum,qzh[200010],qzh2[200010],cc[200010];
struct ll
{
int x,y;
}a[200010];
bool cmp(ll aa,ll bb)//按照位置从小到大来排序
{
return aa.y<bb.y;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>T;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;//输入位置和人数
}
sort(a+1,a+n+1,cmp);//排序后才能保证位置单调性，方便后面二分
for(int i=1;i<=n;i++)
{
cc[i]=a[i].y;//用一个数组存下下标
qzh[i]=qzh[i-1]+a[i].x*a[i].y;//求出前缀和
qzh2[i]=qzh2[i-1]+a[i].x;
}
while(T--)
{
cin>>lc;
int r=lower_bound(cc+1,cc+n+1,lc)-cc;//二分找出第一个大于x的x_i
int q=(lc*qzh2[r-1]-qzh[r-1]),h=((qzh[n]-qzh[r-1])-lc*(qzh2[n]-qzh2[r-1]));//求出答案。q表示左边到目标的距离，h表示右边到目标的距离
cout<<q+h<<"\n";
}
return 0;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...