大庆做网站的公司,佛山,重庆seo外包行者seo06,wordpress+博客+简书问题描述| 试题编号#xff1a; | 201809-2 | | 试题名称#xff1a; | 买菜 | | 时间限制#xff1a; | 1.0s | | 内存限制#xff1a; | 256.0MB | 问题描述 小H和小W来到了一条街上#xff0c;两人分开买菜#xff0c;他们买菜的过程可以描述为#xff0c;去店里买一…问题描述 | 试题编号 | 201809-2 | | 试题名称 | 买菜 | | 时间限制 | 1.0s | | 内存限制 | 256.0MB | 问题描述 小H和小W来到了一条街上两人分开买菜他们买菜的过程可以描述为去店里买一些菜然后去旁边的一个广场把菜装上车两人都要买n种菜所以也都要装n次车。具体的对于小H来说有n个不相交的时间段[a1,b1],[a2,b2]...[an,bn]在装车对于小W来说有n个不相交的时间段[c1,d1],[c2,d2]...[cn,dn]在装车。其中一个时间段[s, t]表示的是从时刻s到时刻t这段时间时长为t-s。 由于他们是好朋友他们都在广场上装车的时候会聊天他们想知道他们可以聊多长时间。 输入格式 输入的第一行包含一个正整数n表示时间段的数量。 接下来n行每行两个数aibi描述小H的各个装车的时间段。 输出格式 输出一行一个正整数表示两人可以聊多长时间。 样例输入 4 1 3 5 6 9 13 14 15 2 4 5 7 10 11 13 14 样例输出 3 数据规模和约定 对于所有的评测用例1 ≤ n ≤ 2000, ai bi ai1ci di ci1,对于所有的i(1 ≤ i ≤ n)有1 ≤ ai, bi, ci, di ≤ 1000000。 题解 因为不清楚给的数据是否有序所以先对左端点进行排序此后分三种情况一种是小H的时间段的右端相交于小W的时间段的内部或者是小H的时间段的右端包含了小W的时间段一种是小W的时间段的右端相交于小H的时间段的内部或者是小W的时间段的右端包含了小H的时间段最后一种是其中一个人的时间段相交于另一个人的两个不同时间段例小H的这一个时间段的右端落在小W的时间段的内部小H的下一个时间段的左端落在小W的时间段的内部就有两部分相交。n 2000 ,可以用两层循环解决第三种情况。代码如下 #include cstdio
#include iostream
#include algorithm
#include string
#include cstring
#include cmath
#include stack
#include vector
#include map
#include set
#include queue
#include utility
#define ll long long
#define ull_ unsigned long longusing namespace std ;const int maxx 2005 ;
int n ;typedef struct{int left ;int right ;
}meassage ;meassage little_H[maxx] , little_W[maxx] ;void init(){for ( int i 0 ; i n ; i ){cin little_H[i].left little_H[i].right ;}for ( int i 0 ; i n ; i ){cin little_W[i].left little_W[i].right ;}return ;
}bool cmp( meassage x , meassage y ){return x.left y.right ;
}void test(){for ( int i 0 ; i n ; i ){cout little_H[i].left little_H[i].right endl ;}cout endl ;for ( int i 0 ; i n ; i ){cout little_W[i].left little_W[i].right endl ;}cout endl ;return ;
}int main(){while ( cin n ){memset(little_H , 0 , sizeof(little_H)) ;memset(little_W , 0 , sizeof(little_W)) ;init() ;sort( little_H , little_H n , cmp ) ;sort( little_W , little_W n , cmp ) ;// test() ;int ans 0 ;for ( int i 0 ; i n ; i ){for ( int j 0 ; j n ; j ){if ( little_H[i].left little_W[j].left little_H[i].right little_W[j].left ){if ( little_H[i].right little_W[j].right ){ans little_H[i].right - little_W[j].left ;}else{ans little_W[j].right - little_W[j].left ;}}else if ( little_W[j].left little_H[i].left little_W[j].right little_H[i].left ){if ( little_W[j].right little_H[i].right ){ans little_W[j].right - little_H[i].left ;}else{ans little_H[i].right - little_H[i].left ;}}}}cout ans endl ;}return 0 ;
} 转载于:https://www.cnblogs.com/Cantredo/p/9839837.html
