逆序对计算的思考 (Tsinghua OJ,PA1)

2024-06-09 09:58

本文主要是介绍逆序对计算的思考 (Tsinghua OJ,PA1),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Tags:Blog


题目出自清华DSA的Programming Assignment作业灯塔(LightHouse).

描述

海上有许多灯塔,为过路船只照明。
图一
如图一所示,每个灯塔都配有一盏探照灯,照亮其东北、西南两个对顶的直角区域。探照灯的功率之大,足以覆盖任何距离。灯塔本身是如此之小,可以假定它们不会彼此遮挡。
图二
若灯塔A、B均在对方的照亮范围内,则称它们能够照亮彼此。比如在图二的实例中,蓝、红灯塔可照亮彼此,蓝、绿灯塔则不是,红、绿灯塔也不是。
现在,对于任何一组给定的灯塔,请计算出其中有多少对灯塔能够照亮彼此。

输入

共n+1行。
第1行为1个整数n,表示灯塔的总数。
第2到n+1行每行包含2个整数x, y,分别表示各灯塔的横、纵坐标。

输出

1个整数,表示可照亮彼此的灯塔对的数量。

样例

Input:

3
2 2
4 3
5 1

Output:

1

限制

对于90%的测例:1 ≤ n ≤ 3×10 5
对于95%的测例:1 ≤ n ≤ 10 6
全部测例:1 ≤ n ≤ 4×10 6
灯塔的坐标x, y是整数,且不同灯塔的x, y坐标均互异
1 ≤ x, y ≤ 10^8
时间:2 sec
内存:256 MB

提示

注意机器中整型变量的范围,C/C++中的int类型通常被编译成32位整数,其范围为[-231, 231 - 1],不一定足够容纳本题的输出。

思考

我们把灯塔坐标抽象为坐标结构体
typedef struct pos{ long x,y; }Pos;
照亮的情况为一个灯塔在另一个灯塔的一四象限,即 tower1.xtower2.x tower1.ytower2.y 同号.
思路一:通过检测每个元素和其他元素的配对情况解决.简单计算知时间复杂度

1+2+3++(n1)=O(n2)

思路二:利用二维线段树求解 暂不详解@XJSoft
思路三:利用逆序对求解.
具体思路为先对X坐标排序,则排好序的数组中一定有 tower_pre.x<tower_suc.x
只要统计Y坐标中前面的元素Y坐标比后面的元素小的即可.则不难得到
Xy,Yy X,Y

ans=n(n1)τ(y1y2y3yn)

Graph-1

如图,X已经排好序,Y坐标为{2,1,3,4} 逆序对数量为1+0+0+0=1
总对数N(N - 1)对,其中不可照亮的有1对,可照亮的有N(N - 1) - 1 = 5对.

代码实现

经过多次优化,把 4×106 的用例用1.3s A掉了.

//CopyRight by XJSoft & ChestnutHeng.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <sys/time.h>
#include <ctype.h>//#define DBG_FLAG    //检测用时
#define ISDIGIT(ch) (ch >= '0' && ch <= '9')
long long detect;
long long start_time;typedef struct pos   //灯塔结构体
{long x,y; 
}Pos;typedef struct parser_ { //解释器,用于快速IOchar *buf;int pos;
} Parser;void read_line(Parser *parser, char *buffer) {gets(buffer);parser->buf = buffer;parser->pos = 0;
}void read_all(Parser *parser, char *buffer) {long sz = 0;long readed;
repeat:                             readed = fread(buffer + sz, 1, 100*1024*1024, stdin);  //100M的缓冲区,一次读完数据if (readed == 0) {buffer[sz] = '\0';goto final;}sz += readed;goto repeat;
final:parser->buf = buffer;parser->pos = 0;
}inline long parse_long(Parser *parser) {while(!(ISDIGIT(parser->buf[parser->pos]) || parser->buf[parser->pos] == '-')) {parser->pos++;}long ret = 0;int sign = 0;if (parser->buf[parser->pos] == '-') {sign = 1;parser->pos++;}while(ISDIGIT(parser->buf[parser->pos])) {ret = ret * 10 + (parser->buf[parser->pos] - '0');parser->pos++;}if (sign) {return -ret;}return ret;
}Pos *temp;
inline int compare(const void *p1, const void *p2) { //本来在Qsort中用的比较函数return (*(Pos*)p1).x - (*(Pos*)p2).x;
}long get_tick_count() {
#ifdef DBG_FLAGstruct timeval tv;gettimeofday(&tv, NULL);return tv.tv_sec * 1000 + tv.tv_usec / 1000;
#elsereturn 0;
#endif
}long read_long() {long ret = 0;while(1) {int ch = fgetc(stdin);if (isdigit(ch)) {ungetc(ch, stdin);break;}}while(1) {int ch = fgetc(stdin);if (isdigit(ch)) {ret = ret * 10 + (ch - '0');} else {return ret;}}
}void debug_time(const char *msg) {
#ifdef DBG_FLAGFILE *fp = fopen("time.log", "a");fprintf(fp, "[%lld] %s\n", get_tick_count() - start_time, msg);fclose(fp);
#endif
}inline long merge(Pos *array,int low,int mid,int high)
{int i = low,j = mid+1,k = low;long count = 0;while(i <= mid && j <= high)if(array[i].y <= array[j].y) {temp[k++] = array[i++];} else{temp[k++] = array[j++];count += j-k;   //逆序数计算}while(i <= mid)temp[k++] = array[i++];while(j <= high)temp[k++] = array[j++];long long st = get_tick_count();memcpy(array + low, temp + low, (high - low + 1) * sizeof(Pos)); //复制数组的优化detect += (get_tick_count() - st);return count;
}long mergeSort(Pos *array,int lo,int hi)
{if(lo<hi){int mid=(lo+hi)>>1;long count=0;count += mergeSort(array,lo,mid);count += mergeSort(array,mid+1,hi);count += merge(array,lo,mid,hi);return count;}return 0;
}void QuickSort(Pos *data, int low, int high) { //手写快排的优化if (low >= high) {return;}int pivot_item = low + rand() % (high - low + 1);Pos swp;swp = data[pivot_item];data[pivot_item] = data[high];data[high] = swp;Pos pivot = data[high];int i, j;i = low;for (j = low; j < high; ++j) {if (data[j].x <= pivot.x) {swp = data[i];data[i] = data[j];data[j] = swp;i++;}}swp = data[i];data[i] = data[high];data[high] = swp;QuickSort(data, low, i - 1);QuickSort(data, i + 1, high);
}int main()
{srand(time(NULL));detect = 0;start_time = get_tick_count();Pos * data = (Pos *)malloc(sizeof(Pos)*4000099);   //数据区debug_time("ALLOC.");int i;int t = 0;long n = 0;long ms;char *all_buf;all_buf = (char*)malloc(100*1024*1024);  //缓冲区Parser parser;read_all(&parser, all_buf);debug_time("RALL.");n = parse_long(&parser);Pos *pointer, *pend = data + n;for (pointer = data; pointer != pend; ++pointer) {  //用解释器读取数据pointer->x = parse_long(&parser);   pointer->y = parse_long(&parser);}free(all_buf);debug_time("READ.");QuickSort(data, 0, n - 1);//  qsort(data,n,sizeof(Pos),compare);#ifdef DBG_FLAGFILE *opt = fopen("sorted.txt", "w");for (pointer = data; pointer != pend; ++pointer) {fprintf(opt, "%ld %ld\n", pointer->x, pointer->y);}fclose(opt);
#endifdebug_time("SORT.");temp = (Pos *)malloc(sizeof(Pos)*4000099);ms = n*(n-1)/2 - mergeSort(data,0,n - 1);printf("%ld\n",ms);
#ifdef DBG_FLAGprintf("%lld\n", detect);
#endifdebug_time("MERGE.");free(data);free(temp);debug_time("ENDED.");return 0;
}

这篇关于逆序对计算的思考 (Tsinghua OJ,PA1)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1044862

相关文章

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 (1)任务并行 (2)数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间,需要在两者之间相互传输数据。 (1)分配GPU内存 (2)将CPU上的数据复制到GPU上 (3)在GPU上对数据进行计算操作 (4)将计算结果从GPU复制到CPU上 (5)释放GPU内存 CUDA内存管理API (1)分配内存 cudaErro

Java - BigDecimal 计算分位(百分位)

日常开发中,如果使用数据库来直接查询一组数据的分位数,就比较简单,直接使用对应的函数就可以了,例如:         PERCENT_RANK() OVER(PARTITION BY 分组列名 ORDER BY 目标列名) AS 目标列名_分位数         如果是需要在代码逻辑部分进行分位数的计算,就需要我们自己写一个工具类来支持计算了 import static ja

OpenStack离线Train版安装系列—2计算节点-环境准备

本系列文章包含从OpenStack离线源制作到完成OpenStack安装的全部过程。 在本系列教程中使用的OpenStack的安装版本为第20个版本Train(简称T版本),2020年5月13日,OpenStack社区发布了第21个版本Ussuri(简称U版本)。 OpenStack部署系列文章 OpenStack Victoria版 安装部署系列教程 OpenStack Ussuri版