首页 > 代码库 > 还不知道是哪里的题目
还不知道是哪里的题目
直接上题目
给出两个由整数组成的集合A, B,计算A ∪ B中包含多少个整数。
Input
输入的第一行包含一个整数T (T > 0),表示一共有T组测试数据。
对于每组测试数据,第一行包含一个整数n (1 ≤ n ≤ 105)。第二行包含2n个整数a1, b1, a2, b2, ..., an, bn (0 < a1 ≤ b1 < a2 ≤ b2 < ... < an ≤ bn < 109),表示A = [a1, b1] ∪ [a2, b2] ∪ ... ∪ [an, bn]。第三行包含一个整数m (1 ≤ m ≤ 105)。第四行包含2m个整数c1, d1, c2, d2, ..., cm, dm (0 < c1 ≤ d1 < c2 ≤ d2 < ... < cm ≤ dm < 109),表示B = [c1, d1] ∪ [c2, d2] ∪ ... ∪ [cm, dm]。
这里[x, y]表示由x, y之间(包含x, y)所有整数组成的集合。
Output
对于每组测试数据,输出A ∪ B中包含多少个整数。
Sample Input
3 1 7 7 1 3 3 2 1 2 3 4 1 2 3 2 1 2 4 6 3 1 3 6 7 9 10
Sample Output
2 4 9
Hint
对样例1的解释:A = {7},B = {3},A ∪ B = {3, 7}。
对样例2的解释:A = {1, 2, 3, 4},B = {2, 3},A ∪ B = {1, 2, 3, 4}。
对样例3的解释:A = {1, 2, 4, 5, 6},B = {1, 2, 3, 6, 7, 9, 10},A ∪ B = {1, 2, 3, 4, 5, 6, 7, 9, 10}。
今天比赛的一道题,一开始题目看错了,结果去求集合A并B 有几个元素。。队友做了半天也没做出来,后来发现是结构体排序的一道题。
思路:如果第一个中输入的元素等于第二个输入中的元素,按第二个元素中降序排。然后用第二个元素中大的直接减掉第一个元素+1就是答案。如果不等于的话,按第一个元素的升序进行排列。比如输入的是六个数,则按第一个,第三个,第五个进行排列,然后判断第二个数是否大于第一个,是的话就减掉+1,然后让第二个元素加1,去找第三个元素是否大于第二个,如果是,则让第四个元素减掉它+1,以此类推。下面上代码!!
#include <stdio.h> #include<algorithm> using namespace std; #define max 200005 struct node { int x,y; } f[max]; bool cmp(node d,node e) { if(d.x!=e.x) return d.x<e.x; else return d.y>e.y; } int main() { int t,i,wbx,sum,cc,c; scanf("%d",&t); while(t--) { sum=0;wbx=0; scanf("%d",&cc); for(i=0;i<cc;i++) scanf("%d%d",&f[i].x,&f[i].y); scanf("%d",&c); for(i=cpl;i<cc+c;i++) scanf("%d%d",&f[i].x,&f[i].y); sort(f,f+cc+c,cmp); for(i=0;i<cpl+cyq;i++) { if(f[i].x>wbx) wbx=f[i].x; if (f[i].y>=wbx) { sum+=f[i].y-wbx+1; wbx=f[i].y+1; } } printf("%d\n",sum); } return 0; }
还不知道是哪里的题目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。