CCF认证201809-2买菜题解——17行代码

欢迎访问我的CCF认证考试题解目录哦 https://blog.csdn.net/richenyunqi/article/details/83385502

题目描述

算法设计

本题实际上可以简化成给出两个区间，求重叠区间长度的问题。 对于给定的两个区间(a,b)和(c,d)，显然，当且仅当$a\le d$且$b\ge c$时才会有重叠区间，此时重叠区间长度L为$$L=min(b,d)-max(a,c)$$由于数据量比较小（最大数据量才2000），故本题可以直接采取暴力搜索的方式，即对于小H的每一个时间段，计算它与小W的每一个时间段的重合区间，时间复杂度为$O(n^2)$。

C++11代码

#include<bits/stdc++.h> using namespace std; int main(){ int n,ans=0;//ans存储最终结果 scanf("%d",&n); vector<pair<int,int>>v1(n),v2(n);//分别存储小H和小W的装车时间段 for(int i=0;i<n;++i) scanf("%d%d",&v1[i].first,&v1[i].second); for(int i=0;i<n;++i) scanf("%d%d",&v2[i].first,&v2[i].second); for(pair<int,int>p1:v1) for(pair<int,int>p2:v2) if(p1.first<=p2.second&&p1.second>=p2.first)//判断有无重叠区间 ans+=min(p1.second,p2.second)-max(p1.first,p2.first);//加上重叠区间 printf("%d",ans); return 0; }