首页 > 代码库 > BZOJ3170: [Tjoi 2013]松鼠聚会
BZOJ3170: [Tjoi 2013]松鼠聚会
3170: [Tjoi 2013]松鼠聚会
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 531 Solved: 249
[Submit][Status]
Description
有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。
Input
第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5
下面N行，每行给出x,y表示其家的坐标。
-10^9<=x,y<=10^9
Output
表示为了聚会走的路程和最小为多少。
Sample Input
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
Sample Output
20
HINT
Source
题解：
我们有两个式子：max（a,b）=（a+b）/2 +|（a-b）/2|
以及：max（|a|,|b|）=|（a+b）/2|+|（a-b）/2|
然后对这题来说dist（i，j）=max（|xi-xj|,|yi-yj|），然后=|（xi-xj+yi-yj）/2|+|（xi-xj-yi+yj）|
我们另x‘=x+y，y’=x-y，则2*dist（i，j）=|xi‘-xj’|+|yi‘-yj’|
然后就可以前缀和后缀和扫一遍得出答案了。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000000000ll 24 25 #define maxn 100000+5 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 struct rec{int x,y;ll z;}a[maxn]; 61 int n; 62 inline bool cmp1(rec a,rec b){return a.x<b.x;} 63 inline bool cmp2(rec a,rec b){return a.y<b.y;} 64 65 int main() 66 67 { 68 69 freopen("input.txt","r",stdin); 70 71 freopen("output.txt","w",stdout); 72 73 n=read(); 74 for1(i,n) 75 { 76 int x=read(),y=read(); 77 a[i].x=x+y;a[i].y=x-y; 78 } 79 sort(a+1,a+n+1,cmp1); 80 ll sum=0; 81 for1(i,n) 82 { 83 a[i].z+=(ll)a[i].x*(ll)(i-1)-sum; 84 sum+=(ll)a[i].x; 85 } 86 sum=0; 87 for3(i,n,1) 88 { 89 a[i].z+=sum-(ll)a[i].x*(ll)(n-i); 90 sum+=(ll)a[i].x; 91 } 92 sort(a+1,a+n+1,cmp2); 93 sum=0; 94 for1(i,n) 95 { 96 a[i].z+=(ll)a[i].y*(ll)(i-1)-sum; 97 sum+=(ll)a[i].y; 98 } 99 sum=0;100 for3(i,n,1)101 {102 a[i].z+=sum-(ll)a[i].y*(ll)(n-i);103 sum+=(ll)a[i].y;104 }105 ll ans=inf;106 for1(i,n)ans=min(ans,a[i].z);107 printf("%lld\n",ans>>1);108 109 return 0;110 111 }
BZOJ3170: [Tjoi 2013]松鼠聚会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。