【CSP CCF记录】201809-2第14次认证 买菜
题目
样例输入
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
样例输出
3
思路
易错点：仅考虑所给样例，会误以为H和W两人的装车时间是一一对应的，那么提交结果的运行错误就会让你瞬间清醒。
本题关键是认识到H和W的装车时间不一定一一对应，需要使用k1,k2两个不同的迭代变量分别标记两人的装车时间片。
主要分为以下两种情况：
H一个装车时间片可能对应好几个W的装车时间片，因此，若W的某次装车率先结束而H的本次装车并未结束，即h[k1].end>w[k2].end，就需要k2++。
代码
数组写法
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=2010;
int main()
{
int a[N],b[N],c[N],d[N];
cin>>n;
for(int i=0;i<n;i++)//小H的装车时间段
{
cin>>a[i]>>b[i];
}
for(int i=0;i<n;i++)//小W的装车时间段
{
cin>>c[i]>>d[i];
}
long long ans=0;
int k1=0,k2=0;
while(k1<n&&k2<n)
{
//1.H和W的两段装车时间完全不相交
if(b[k1]<c[k2])k1++;
else if(d[k2]<a[k1])k2++;
else//2.H和W的两段装车时间有相交
{
int temp1,temp2;
temp1=max(a[k1],c[k2]);
temp2=min(b[k1],d[k2]);
ans+=(temp2-temp1);
if(b[k1]<d[k2])k1++;
else k2++;
}
}
cout<<ans;
return 0;
}结构体写法
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
struct time{
int beg,end;
}h[N],w[N];
int main(){
int n;
long long ans=0;
int k1=0,k2=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>h[i].beg>>h[i].end;
}
for(int i=0;i<n;i++){
cin>>w[i].beg>>w[i].end;
}
while(k1<n&&k2<n){
if(h[k1].end<w[k2].beg)k1++;
else if(w[k2].end<h[k1].beg)k2++;
else{
int temp1,temp2;
temp1=max(h[k1].beg,w[k2].beg);
temp2=min(h[k1].end,w[k2].end);
ans+=(temp2-temp1);
if(h[k1].end<w[k2].end)k1++;
else k2++;
}
}
cout<<ans;
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].end<w[k2].end)k1++;
else k2++;而我写成了
if(h[k1].end<w[k2].end)k1++;
else if(h[k1].end>w[k2].end)k2++;显然我没有考虑到h[k1].end=w[k2].end的情况，导致好几个用例运行时间过长，真是失之毫厘，谬以千里，特此记录，引起注意。
原文地址：https://blog.csdn.net/m0_73733846/article/details/144030371
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！