网站如何更换服务器,静态单页网站wordpress,小程序开发教程推荐,教育行业网站题意及思路 题意#xff1a;有N个节点#xff08;1至N#xff09;#xff0c;求给定的st号到en号的距离最小值#xff0c;这些点构成一个环#xff0c;即1-2 ... -N -1。 思路#xff1a;第一步#xff0c;预处理操作#xff0c;以dis[ i ] 表示#xff… 题意及思路 题意有N个节点1至N求给定的st号到en号的距离最小值这些点构成一个环即1-2 ... -N -1。 思路第一步预处理操作以dis[ i ] 表示第1号节点到 i 所指的下一个节点的距离顺时针的下一个位置同时记录环的总距离sum。第二步计算给定请求的两点距离最短和由公式可得dis[ en - 1 ] - dis [ st - 1 ] 。最终取前面所得值t 和 sum - t 的较小值即可。公式需要想一想下面附上了思维草图很不严谨 注意点第一点st en注意大小若st en 则交换。第二点虽然这题就是一个简单的模拟但是给定的范围蛮大如果使用遍历数组On复杂度的暴力法无法在给定时限内完成所以这题的关键在于预处理操作。 附上思维草图右边红色部分是例子 代码 #include iostream
#include algorithmusing namespace std;const int MAX 100005;
int dis[MAX],arr[MAX];int main(){int n;cin n;int sum 0;for(int i1;in;i) {cin arr[i];sum arr[i];dis[i] sum; //key code}int m,st,en;cin m;while(m--){cin st en;if(sten) swap(st,en);int t dis[en-1] - dis[st-1];cout min(t,sum-t) endl;}return 0;
} 转载于:https://www.cnblogs.com/kyrie211/p/11288667.html
