在一条线上,给定一些区间和点,每个区间长度给定,位置可以任意选择,问这些区间能不能覆盖所有点?求思路,网上一搜全是区间覆盖问题,根本搜不到
1条回答 默认 最新
- 赵4老师 2022-08-12 11:29关注
仅供参考:
//实现一个函数:求数轴上多个线段覆盖的区域对应的多个线段; 输入多个线段,求出被这些线段覆盖的所有区域(也用线段表示); 一条线段用两个值表示(x0,x1), 其中x1>x0; //比如(1,3);(2,4);(5,6);结果为(1,4);(5,6); //比如(1,3);(2,4);(5,6);(4,7);结果为(1,7); #include <stdio.h> #define MAXLINES 100 struct LINE { int x0;//左端 int x1;//右端 } ls[MAXLINES]; int i,j,k,n,x0,x1,c; void add() { if (0==n) {//加入第一对点 ls[n].x0=x0; ls[n].x1=x1; n=1; } else { if (x1==ls[0].x0) {//右端=第一条线段的左端 ls[0].x0=x0;//第一条线段的左端修改为左端 return; } if (x1<ls[0].x0) {//右端<第一条线段的左端 for (i=n-1;i>=0;i--) {//将所有线段往后移 ls[i+1].x0=ls[i].x0; ls[i+1].x1=ls[i].x1; } ls[0].x0=x0;//新第一条线段为x0,x1 ls[0].x1=x1; n++; return; } if (ls[n-1].x1<x0) {//左端>最后那条线段的右端 ls[n].x0=x0;//新最后那条线段 ls[n].x1=x1; n++; return; } if (x0<=ls[0].x0 && ls[n-1].x1<=x1) {//左端≤第一条线段的左端且最后那条线段的右端≤右端 ls[0].x0=x0;//只剩这一条线段 ls[0].x1=x1; n=1; return; } for (i=0;i<n;i++) {//从左到右依次检查每条线段 if (ls[i].x0<=x0 && x0<=ls[i].x1) {//第i条线段的左端≤左端≤第i条线段的右端 for (j=i;j<n;j++) {//从第i条线段开始从左到右依次检查每条线段 if (ls[j].x0<=x1 && x1<=ls[j].x1) {//第j条线段的左端≤右端≤第j条线段的右端 ls[i].x1=ls[j].x1;//第i条线段的右端改为第j条线段的右端 for (k=1;k<=n-j-1;k++) {//将剩余线段往前移 ls[i+k].x0=ls[j+k].x0; ls[i+k].x1=ls[j+k].x1; } n-=j-i; return; } if (ls[j].x1<x1 && (j==n-1 || x1<ls[j+1].x0)) {//第j条线段的右端<右端<第j+1条线段的左端(如果有) ls[i].x1=x1;//第i条线段的右端改为右端 for (k=1;k<=n-j-1;k++) {//将剩余线段往前移 ls[i+k].x0=ls[j+k].x0; ls[i+k].x1=ls[j+k].x1; } n-=j-i; return; } } } if (ls[i].x1<x0 && (i==n-1 || x0<ls[i+1].x0)) {//第i条线段的右端<左端<第i+1条线段的左端(如果有) if (i!=n-1 && x1<ls[i+1].x0) {//右端<第i+1条线段的左端(如果有) for (k=n-1;k>=i+1;k--) {//将从第i+1条线段开始的所有线段往后移 ls[k+1].x0=ls[k].x0; ls[k+1].x1=ls[k].x1; } ls[i+1].x0=x0;//新第i+1条线段为x0,x1 ls[i+1].x1=x1; n++; return; } for (j=i+1;j<n;j++) {//从第i+1条线段开始从左到右依次检查每条线段 if (ls[j].x0<=x1 && x1<=ls[j].x1) {//第j条线段的左端≤右端≤第j条线段的右端 ls[i+1].x0=x0;//第i+1条线段的左端改为左端 ls[i+1].x1=ls[j].x1;//第i+1条线段的右端改为第j条线段的右端 for (k=1;k<=n-j-1;k++) {//将剩余线段往前移 ls[i+1+k].x0=ls[j+k].x0; ls[i+1+k].x1=ls[j+k].x1; } n-=j-i-1; return; } if (ls[j].x1<x1 && (j==n-1 || x1<ls[j+1].x0)) {//第j条线段的右端<右端<第j+1条线段的左端(如果有) ls[i+1].x0=x0;//第i+1条线段的左端改为左端 ls[i+1].x1=x1;//第i+1条线段的右端改为右端 for (k=1;k<n-j-1;k++) {//将剩余线段往前移 ls[i+k].x0=ls[j+k].x0; ls[i+k].x1=ls[j+k].x1; } n-=j-i-1; return; } } } if (x0<ls[i].x0) {//左端<第i条线段的左端 for (j=i;j<n;j++) {//从第i条线段开始从左到右依次检查每条线段 if (ls[j].x0<=x1 && x1<=ls[j].x1) {//第j条线段的左端≤右端≤第j条线段的右端 ls[i].x0=x0;//第i条线段的左端改为左端 ls[i].x1=ls[j].x1;//第i条线段的右端改为第j条线段的右端 for (k=1;k<=n-j-1;k++) {//将剩余线段往前移 ls[i+k].x0=ls[j+k].x0; ls[i+k].x1=ls[j+k].x1; } n-=j-i; return; } if (ls[j].x1<x1 && (j==n-1 || x1<ls[j+1].x0)) {//第j条线段的右端<右端<第j+1条线段的左端(如果有) ls[i].x0=x0;//第i条线段的左端改为左端 ls[i].x1=x1;//第i条线段的右端改为右端 for (k=1;k<=n-j-1;k++) {//将剩余线段往前移 ls[i+k].x0=ls[j+k].x0; ls[i+k].x1=ls[j+k].x1; } n-=j-i; return; } } } } } } void show() { for (i=0;i<n;i++) { printf("(%d,%d);",ls[i].x0,ls[i].x1); } printf("\n"); } void main() { n=0; c=0; while (1) { printf("Input x0,x1(x0<x1;0,0 to exit):"); fflush(stdout); rewind(stdin); if (2==scanf("%d,%d",&x0,&x1)) { if (0==x0&&0==x1) break; if (x1>x0) { c++; if (c>=MAXLINES) { printf("Up to %d!\n",MAXLINES); break; } add(); show(); } } } }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用
悬赏问题
- ¥15 想问一下树莓派接上显示屏后出现如图所示画面,是什么问题导致的
- ¥100 嵌入式系统基于PIC16F882和热敏电阻的数字温度计
- ¥15 cmd cl 0x000007b
- ¥20 BAPI_PR_CHANGE how to add account assignment information for service line
- ¥500 火焰左右视图、视差(基于双目相机)
- ¥100 set_link_state
- ¥15 虚幻5 UE美术毛发渲染
- ¥15 CVRP 图论 物流运输优化
- ¥15 Tableau online 嵌入ppt失败
- ¥100 支付宝网页转账系统不识别账号