最新消息: 电脑我帮您提供丰富的电脑知识,编程学习,软件下载,win7系统下载。

【WZOI第二次NOIP模拟赛Day1T2】世界末日解题报告

IT培训 admin 2浏览 0评论

【WZOI第二次NOIP模拟赛Day1T2】世界末日 解题报告

【WZOI第二次NOIP模拟赛Day1T2】世界末日

Problem 2 世界末日 (doomsday.pas/c/cpp) 

背景

话说CWQ大牛终于打开了那扇神秘大门,但迎接他的不是什么神秘的东西,而是一大群外星入侵者,WZland岌岌可危…..(这里说一下为什么外星人不自己打开那扇神秘大门呢?
因为在开辟通道的时候他们不小心将门装反了,这才会有CWQ破密码这一出。) 


问题描述

WZland的国王向来喜爱和平,他不想与外星人正面冲突,于是他决定不和外星人战斗而采用躲避的方式来逃过这一劫难。
WZland的国王想找到一个地方(其实是新建一个避难所)来让WZland的所有人藏身。这一个伟大的任务就交给了WZOI应急小组的成员来完成。
话说WZland的版图是一个N×M的矩形,然后WZland被分成N×M块正方形的土地。在某些土地上是有WZland的居民居住的,但某些土地是荒地没有任何人居住(WZland的土地可
以用一个二元组(X,Y)来描述,表示这块土地处于第X行,第Y列)。
WZland的国王希望找到一个地方建立一个紧急避难所,他要求所有人走过的路程最短。
如果土地1的坐标为(X1,Y1),土地2的坐标为(X2,Y2),那么从土地1到土地2的路程为|X1-X2|+|Y1-Y2|。
时间十分紧迫,WZOI的成员只有1s的时间来解决这个问题。


输入格式

输入数据第一行包含3个整数N,M,T,分别表示WZland版图的大小和有人居住的土地的个数;
第2行到第T+1行,每行包含3个整数X,Y,P(1≤X≤N, 1≤Y≤M),分别表示土地的坐标和居住在这块土地的人数。输入数据保证同一块土地不会被多次描述。


输出格式

输出数据只包含一行,1个实数S,分别表示所有人到达紧急避难所所走的距离之和(结果保留两位小数)。


样例输入输出

Sample #1 
doomsday.in  doomsday.out 
1 1 1 
1 1 
0.00 
Sample #2 
doomsday.in  doomsday.out 
5 6 3 
1 2 1 
3 4 2 
1 3 4 
7.00 

数据规模

对于30%的数据,N,M≤1000,T≤200;
对于50%的数据,N,M≤1000000,T≤5000;
对于100%的数据,N,M≤10000000,T≤200000;
对于100%的数据,P≤1000000。

时间限制

1s

 

【解题思路】

加权中位数;

我们可以知道x和y坐标可以是独立的,就是我们可以先求出x坐标再求出y坐标;

先求出总人数sum;

先把每一个点按照x坐标排序,然后从左往右扫,把每一个点上的人数加和,一直到和>=(sum+1)/2退出,当前点的x坐标就是“避难所”的x坐标;

然后把每一个点按照y坐标排序,然后从左往右扫,把每一个点上的人数加和,一直到和>=(sum+1)/2退出,当前点的y坐标就是“避难所”的y坐标;

那么我们现在确定了这个点的位置,只需要计算就可以了;

还可以这样来理解:我们先求一下所有人 走到一条横着的线上最小是哪里,再求一下所有人走到一条竖着的线上最小是哪里,这一横一竖就能确定一个点的位置;

【代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct hp{
<span style="white-space:pre">	</span>int x,y,num;
}a[200005];
long long n,m,t,i,sum,mid,b,xx,yy;
double ans;int cmp1(hp a,hp b)
{
<span style="white-space:pre">	</span>return a.x<b.x;
}int cmp2(hp a,hp b)
{
<span style="white-space:pre">	</span>return a.y<b.y;
}int main()
{
<span style="white-space:pre">	</span>freopen("doomsday.in","r",stdin);
<span style="white-space:pre">	</span>freopen("doomsday.out","w",stdout);
<span style="white-space:pre">	</span>cin>>n>>m>>t;
<span style="white-space:pre">	</span>for (i=1;i<=t;++i)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">	</span>  cin>>a[i].x>>a[i].y>>a[i].num;
<span style="white-space:pre">	</span>  sum+=a[i].num;}mid=(sum+1)/2;
<span style="white-space:pre">	</span>sort(a+1,a+t+1,cmp1);
<span style="white-space:pre">	</span>b=0;
<span style="white-space:pre">	</span>i=0;
<span style="white-space:pre">	</span>while (b<mid)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>i++;
<span style="white-space:pre">		</span>b+=a[i].num;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>xx=a[i].x;
<span style="white-space:pre">	</span>sort(a+1,a+t+1,cmp2);
<span style="white-space:pre">	</span>b=0;
<span style="white-space:pre">	</span>i=0;
<span style="white-space:pre">	</span>while (b<mid)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>i++;
<span style="white-space:pre">		</span>b+=a[i].num;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>yy=a[i].y;
<span style="white-space:pre">	</span>ans=0;
<span style="white-space:pre">	</span>for (i=1;i<=t;++i)
<span style="white-space:pre">	</span>  ans+=a[i].num*(abs(a[i].x-xx)+abs(a[i].y-yy))+0.00;
<span style="white-space:pre">	</span>printf("%0.2lf",ans);
<span style="white-space:pre">	</span>return 0;
}

【犯的错误】

中间量会爆int,中间量必须开long long;窝开始就写了标算,结果就是因为开了int结果被卡成了30分;

woc被卡到30分的赶脚很不爽。。

【WZOI第二次NOIP模拟赛Day1T2】世界末日 解题报告

【WZOI第二次NOIP模拟赛Day1T2】世界末日

Problem 2 世界末日 (doomsday.pas/c/cpp) 

背景

话说CWQ大牛终于打开了那扇神秘大门,但迎接他的不是什么神秘的东西,而是一大群外星入侵者,WZland岌岌可危…..(这里说一下为什么外星人不自己打开那扇神秘大门呢?
因为在开辟通道的时候他们不小心将门装反了,这才会有CWQ破密码这一出。) 


问题描述

WZland的国王向来喜爱和平,他不想与外星人正面冲突,于是他决定不和外星人战斗而采用躲避的方式来逃过这一劫难。
WZland的国王想找到一个地方(其实是新建一个避难所)来让WZland的所有人藏身。这一个伟大的任务就交给了WZOI应急小组的成员来完成。
话说WZland的版图是一个N×M的矩形,然后WZland被分成N×M块正方形的土地。在某些土地上是有WZland的居民居住的,但某些土地是荒地没有任何人居住(WZland的土地可
以用一个二元组(X,Y)来描述,表示这块土地处于第X行,第Y列)。
WZland的国王希望找到一个地方建立一个紧急避难所,他要求所有人走过的路程最短。
如果土地1的坐标为(X1,Y1),土地2的坐标为(X2,Y2),那么从土地1到土地2的路程为|X1-X2|+|Y1-Y2|。
时间十分紧迫,WZOI的成员只有1s的时间来解决这个问题。


输入格式

输入数据第一行包含3个整数N,M,T,分别表示WZland版图的大小和有人居住的土地的个数;
第2行到第T+1行,每行包含3个整数X,Y,P(1≤X≤N, 1≤Y≤M),分别表示土地的坐标和居住在这块土地的人数。输入数据保证同一块土地不会被多次描述。


输出格式

输出数据只包含一行,1个实数S,分别表示所有人到达紧急避难所所走的距离之和(结果保留两位小数)。


样例输入输出

Sample #1 
doomsday.in  doomsday.out 
1 1 1 
1 1 
0.00 
Sample #2 
doomsday.in  doomsday.out 
5 6 3 
1 2 1 
3 4 2 
1 3 4 
7.00 

数据规模

对于30%的数据,N,M≤1000,T≤200;
对于50%的数据,N,M≤1000000,T≤5000;
对于100%的数据,N,M≤10000000,T≤200000;
对于100%的数据,P≤1000000。

时间限制

1s

 

【解题思路】

加权中位数;

我们可以知道x和y坐标可以是独立的,就是我们可以先求出x坐标再求出y坐标;

先求出总人数sum;

先把每一个点按照x坐标排序,然后从左往右扫,把每一个点上的人数加和,一直到和>=(sum+1)/2退出,当前点的x坐标就是“避难所”的x坐标;

然后把每一个点按照y坐标排序,然后从左往右扫,把每一个点上的人数加和,一直到和>=(sum+1)/2退出,当前点的y坐标就是“避难所”的y坐标;

那么我们现在确定了这个点的位置,只需要计算就可以了;

还可以这样来理解:我们先求一下所有人 走到一条横着的线上最小是哪里,再求一下所有人走到一条竖着的线上最小是哪里,这一横一竖就能确定一个点的位置;

【代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct hp{
<span style="white-space:pre">	</span>int x,y,num;
}a[200005];
long long n,m,t,i,sum,mid,b,xx,yy;
double ans;int cmp1(hp a,hp b)
{
<span style="white-space:pre">	</span>return a.x<b.x;
}int cmp2(hp a,hp b)
{
<span style="white-space:pre">	</span>return a.y<b.y;
}int main()
{
<span style="white-space:pre">	</span>freopen("doomsday.in","r",stdin);
<span style="white-space:pre">	</span>freopen("doomsday.out","w",stdout);
<span style="white-space:pre">	</span>cin>>n>>m>>t;
<span style="white-space:pre">	</span>for (i=1;i<=t;++i)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">	</span>  cin>>a[i].x>>a[i].y>>a[i].num;
<span style="white-space:pre">	</span>  sum+=a[i].num;}mid=(sum+1)/2;
<span style="white-space:pre">	</span>sort(a+1,a+t+1,cmp1);
<span style="white-space:pre">	</span>b=0;
<span style="white-space:pre">	</span>i=0;
<span style="white-space:pre">	</span>while (b<mid)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>i++;
<span style="white-space:pre">		</span>b+=a[i].num;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>xx=a[i].x;
<span style="white-space:pre">	</span>sort(a+1,a+t+1,cmp2);
<span style="white-space:pre">	</span>b=0;
<span style="white-space:pre">	</span>i=0;
<span style="white-space:pre">	</span>while (b<mid)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>i++;
<span style="white-space:pre">		</span>b+=a[i].num;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>yy=a[i].y;
<span style="white-space:pre">	</span>ans=0;
<span style="white-space:pre">	</span>for (i=1;i<=t;++i)
<span style="white-space:pre">	</span>  ans+=a[i].num*(abs(a[i].x-xx)+abs(a[i].y-yy))+0.00;
<span style="white-space:pre">	</span>printf("%0.2lf",ans);
<span style="white-space:pre">	</span>return 0;
}

【犯的错误】

中间量会爆int,中间量必须开long long;窝开始就写了标算,结果就是因为开了int结果被卡成了30分;

woc被卡到30分的赶脚很不爽。。

发布评论

评论列表 (0)

  1. 暂无评论