上传网站步骤,html5网站基础,佛山网站建设及优化公司,怎么给网站做php后台题干#xff1a;
X轴上有N条线段#xff0c;每条线段包括1个起点和终点。线段的重叠是这样来算的#xff0c;[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点#xff0c;从中选出2条线段#xff0c;这两条线段的重叠部分是最长的。输出这个最长的距离。如…题干
X轴上有N条线段每条线段包括1个起点和终点。线段的重叠是这样来算的[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点从中选出2条线段这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠输出0。 Input 第1行线段的数量N(2 N 50000)。 第2 - N 1行每行2个数线段的起点和终点。(0 s , e 10^9) Output 输出最长重复区间的长度。 Input示例 5 1 5 2 4 2 8 3 7 7 9 Output示例
4 解题报告
区间问题先想到排序此题以起点为标准排序优点排完后只需要o(n)看右端点即可总体复杂度o(nlognn)。如果不排序直接暴搜复杂度是o(n^2)。
ac代码
#includeiostream
#includecstdio
#includealgorithm
using namespace std;struct Node {int s,e;
} node[500005];//没有逗号(格式问题要记牢啊)
bool cmp(const Node a,const Node b) {if(a.s!b.s) return a.sb.s;else return a.eb.e;
}
int main()
{int maxx0;int n;cinn;for(int i 1; in; i) {scanf(%d %d,node[i].s,node[i].e);}//相当于以起点开始的dp搜索以node[i].s为起点或者说当前的l的最大公共区间部分 sort(node1,noden1,cmp);//排序的好处还有一个就是已于看清最大公共区间的可能范围因为你以起点排序了所以只需要排相邻两者即可而不需要每一个都搜索一遍n那样复杂度是n^2了排序再算就是o(nlognn) int lnode[1].s,rnode[1].e;for(int i 2; in; i) {if(node[i].er) {//maxx应该不变不对 还是有可能变化的 maxxmax(maxx,r-node[i].s);}else if(node[i].er) { // 别忘号不然就wa了 maxxmax(maxx,node[i].e-node[i].s);}rmax(r,node[i].e);}printf(%d\n,maxx);return 0 ;}
一个网络版的for循环结构是这样的
for(int i1;in;i){if(sf[i].s ef[i].e)sume-f[i].s;else if(sf[i].s ef[i].e)sumf[i].e-f[i].s;maxxmax(maxx,sum);if(ef[i].e)continue;sf[i].s;ef[i].e;}
感觉这样写并不好因为此处肯本不需要s的参与因为你排好序了啊
