【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的情况，导致好几个用例运行时间过长，真是失之毫厘，谬以千里，特此记录，引起注意。