【复试刷题】贪心法搬桌子问题 | 您所在的位置:网站首页 › 往右走的标志 › 【复试刷题】贪心法搬桌子问题 |
题目描述
某教学大楼一层有n个教室,从左到右依次编号为1、2、…、n。现在要把一些课桌从某些教室搬到另外一些教室,每张桌子都是从编号较小的教室搬到编号较大的教室,每一趟,都是从左到右走,搬完一张课桌后,可以继续从当前位置或往右走搬另一张桌子。 输入数据:先输入n、m,然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。 输出数据:最少需要跑几趟。 题意分析例如有10个教室,有4张桌子要搬 起始终点13243946
用结构体表示桌子,用到了c里面的qsort函数,这个要记一下cmp要怎么改。核心代码看的网上的,自己想得太歪了。 #include #include #include //贪心实现搬桌子,每次搬运离当前桌子最近的桌子 typedef struct desk { int start; int end; }desk; // 结构体排序 int cmp(void const* a,void const* b) { desk *p=(desk*)a; desk *q=(desk*)b; if(p->start!=q->start) return (p->start)-(q->start); else return (p->end)-(q->end); } int main() { int rooms=0,desks=0; FILE* fp=fopen("./data.txt","r"); fscanf(fp,"%d %d\n",&rooms,&desks); // 结构体数组存放desks desk *dsk = (desk*)malloc(sizeof(desk)*desks); int *isMove=(int*)malloc(sizeof(int)*desks); //桌子是否搬走 for(int i=0;i int temp = 0; for (int i = 0; i // 下一个位置 temp = dsk[i].end; isMove[i] = 1; num++; } } count++; } printf("%d",count); getchar(); } 输入 |
CopyRight 2018-2019 实验室设备网 版权所有 |