网站怎么才能被百度收录,无法更新网站主页 dedecms,市住房城乡建设网站,wordpress cms 比较CSDN竞赛68期 CSDN竞赛68期1.小球游戏2.王子闯闸门分析 CSDN竞赛68期
1.小球游戏
这个是64期的题目#xff0c;完全一样#xff0c;有点无语了#xff0c;竟然又出了#xff0c;真不知道怎么出的题。 参考#xff1a;CSDN周赛64期
2.王子闯闸门
波斯王子要去救被贾法尔… CSDN竞赛68期 CSDN竞赛68期1.小球游戏2.王子闯闸门分析 CSDN竞赛68期
1.小球游戏
这个是64期的题目完全一样有点无语了竟然又出了真不知道怎么出的题。 参考CSDN周赛64期
2.王子闯闸门
波斯王子要去救被贾法尔囚禁的公主但贾法尔用黑魔法在他面前设置了编号从1到n的n道闸门。从王子的位置到1号闸门需要1秒从n号闸门到公主所在的位置也需要1秒从p号闸门到p1或p-1号闸门都需要1秒。 每过1秒钟王子都必须决定选择前进一道闸门、后退一道闸门或停在原地这三种动作中的一种。当然王子不能选择移动到关闭状态的闸门而只能选择开启状态的闸门。在王子做出动作选择后闸门也可能会有关闭和开启的动作如果王子做完动作后其所在的闸门在该秒内的动作是从开启变为关闭则他就会被闸门夹死。 现在给出闸门数量n和m个闸门的动作时刻表求波斯王子需要多少秒才能救出公主。
分析
这道题逻辑很简单在t时间时在p位置那么有三个选择如果t1时p1的门未关闭则到p1的位置如果t1时p1的门会关闭则再检查p位置在t1时是否会关闭如果不关留在p位置如果关闭退到p-1的位置如果p-1的位置也关闭会死掉这时说明进入p位置的时间不对那么回退到在p-1位置的最后时间进入到p位置的前一秒这时不应该进入p位置而是在p-1位置上多等1s这可能不是最优解但有可能避免挂掉的可能。这就需要记住在每个位置上的时间。
在考试的时候我按照上面的逻辑写出来了但是会超时因为每一秒都需要查询关闭时间表而每次都要m次因为有m个时刻表。在考试结束后想到的方法是优化查询时刻表。首先对时刻表根据门编号排序然后用数组x[n2][2]来记录每一个位置编号在时刻表中的起始和结束位置。因为考试结束没法再用考试的测试用例所以不能保证完全对代码如下
#include stdio.h
#include stdlib.h
#include stdbool.h
#include string.h
#include math.hstruct close_info{int num; // 门编号int close_s; // 门关闭的开始时间int close_e; // 门关闭的结束时间
};// 检查门是否会关闭
bool check_will_close(struct close_info info[], int x[][2], int pos, int time)
{if (x[pos][0] -1) // 没有记录关闭时间代表一直打开return false;else{for (int i x[pos][0]; i x[pos][1]; i){if (time info[i].close_s time info[i].close_e){return true;}}}return false;
}int cmp(const void *a, const void *b)
{int num1 ((struct close_info *)a)-num;int num2 ((struct close_info *)b)-num;return num1-num2;
}int main()
{int n,m;struct close_info *info;scanf(%d %d,n, m);info (struct close_info *)malloc(sizeof(struct close_info)*m);for (int i 0; i m; i) {scanf(%d %d %d,info[i].num,info[i].close_s,info[i].close_e);}// 对info进行排序qsort(info,m,sizeof(struct close_info),cmp);// for (int i 0; i m; i)// {// printf(info[%d].num%d,info[%d].close_s%d,info[%d].close_e%d\n,i,info[i].num,i,info[i].close_s,i,info[i].close_e);// }// 记录每道闸门的信息在info中的位置int total n2; // 位置编号是0-(n1)int x[total][2]; // 在info中从x[i][0]到x[i][1]都是闸门i的时刻表 for (int i 0; i total; i) // 初始化{x[i][1] x[i][0] -1;}for (int i 0; i m; i){if (x[info[i].num][0] -1)x[info[i].num][0] i;x[info[i].num][1] i;}// for (int i 0; i total; i)// {// printf(x[%d][0]%d,x[%d][1]%d\n,i,x[i][0],i,x[i][1]);// }int pos 0;int time 0;int end n 1;int pos_time[total]; // 最后一次在i位置的时间int dead_count 0;// int dead_pos;while (pos end) {time;if (dead_count 0 !check_will_close(info, x, pos1, time)) // 前面的门不会关闭 {pos;pos_time[pos] time;continue;}dead_count 0;// else {if (!check_will_close(info, x, pos, time)) //当前的门不关闭留在这{pos_time[pos] time;} else // 当前关闭 {if (!check_will_close(info, x,pos-1, time)) // 后面不关闭 {pos--;pos_time[pos] time;continue;}else // 死路 {// 时光回溯回到前一格的位置和时间点然后选择不前进到下一个门pos--;time pos_time[pos];dead_count 1;}}}}printf(%d\n,time);
}
