网站建设的目的,wordpress 给文件命名,网站建设与维护学什么科目,做一个小说网站需要多少钱题目 样例输入 4 1 3 5 6 9 13 14 15 2 4 5 7 10 11 13 14 样例输出 3 思路
易错点#xff1a;仅考虑所给样例#xff0c;会误以为H和W两人的装车时间是一一对应的#xff0c;那么提交结果的运行错误就会让你瞬间清醒。
本题关键是认识到H和W的装车时间不一定一一对应仅考虑所给样例会误以为H和W两人的装车时间是一一对应的那么提交结果的运行错误就会让你瞬间清醒。
本题关键是认识到H和W的装车时间不一定一一对应需要使用k1,k2两个不同的迭代变量分别标记两人的装车时间片。
主要分为以下两种情况 H一个装车时间片可能对应好几个W的装车时间片因此若W的某次装车率先结束而H的本次装车并未结束即h[k1].endw[k2].end就需要k2。
代码
数组写法
#includebits/stdc.h
using namespace std;
int n;
const int N2010;
int main()
{int a[N],b[N],c[N],d[N];cinn;for(int i0;in;i)//小H的装车时间段 {cina[i]b[i];}for(int i0;in;i)//小W的装车时间段 {cinc[i]d[i];}long long ans0;int k10,k20;while(k1nk2n){//1.H和W的两段装车时间完全不相交 if(b[k1]c[k2])k1;else if(d[k2]a[k1])k2;else//2.H和W的两段装车时间有相交 {int temp1,temp2;temp1max(a[k1],c[k2]);temp2min(b[k1],d[k2]);ans(temp2-temp1);if(b[k1]d[k2])k1;else k2;}} coutans;return 0;
}
结构体写法
#includebits/stdc.h
using namespace std;
const int N2010;
struct time{int beg,end;
}h[N],w[N];
int main(){int n;long long ans0;int k10,k20; cinn;for(int i0;in;i){cinh[i].begh[i].end;}for(int i0;in;i){cinw[i].begw[i].end;}while(k1nk2n){if(h[k1].endw[k2].beg)k1;else if(w[k2].endh[k1].beg)k2;else{int temp1,temp2;temp1max(h[k1].beg,w[k2].beg);temp2min(h[k1].end,w[k2].end);ans(temp2-temp1);if(h[k1].endw[k2].end)k1;else k2;}}coutans; return 0;
} 运行结果
数组写法 结构体写法 反思1——用结构体代替多个数组减少运行时间
理论上说定义多个数组可能会导致运行时间过长的原因通常涉及到 内存访问效率 和 数据局部性 的问题。而使用 结构体 替代多个数组可以通过改善数据的布局和内存访问模式来提高程序的性能减少运行时间。
假设你在代码中定义了多个数组类似于以下的情况
int x[1000];
int y[1000];
int z[1000];每个数组是一个独立的内存块存储在内存中的位置可能相隔较远。这种布局会导致以下几个问题
内存访问局部性差数据不连续增加了缓存未命中的概率内存对齐问题
如果这些数组彼此之间的元素是相关联的比如三维空间中的一个点就可以使用结构体可以将相关的数据放到一个内存结构中从而减少内存分散提高内存访问效率。
struct Point {int x;int y;int z;
};Point points[1000];在本题中可以对比“数组写法”和“结构体写法”的运行时间虽然这种改进微乎其微但是为我们提供了一个减少运行时间的思路。
反思2——在使用if语句时注意对所有情况进行全面的讨论
这道简单题卡壳了很长时间最终发现是出现了以下的小错误
正确写法
if(h[k1].endw[k2].end)k1;
else k2;
而我写成了
if(h[k1].endw[k2].end)k1;
else if(h[k1].endw[k2].end)k2;
显然我没有考虑到h[k1].endw[k2].end的情况导致好几个用例运行时间过长真是失之毫厘谬以千里特此记录引起注意。
