第一周算法设计与分析 D : 两面包夹芝士

D : 两面包夹芝士

Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 85 Solved: 31

Description

给你两个长度为N的整型(int)数组A = (A1, A2, A3, …, An) 和 B = (B1, B2, B3, …, Bn) 请你找出有多少整型(int)数字x，满足Ai ≤ x ≤ Bi，其中 1≤ i  ≤ N

Input

第一行输入N，第二行输入N个数字Ai，第三行输入N个数字Bi

• 1 ≤ N ≤ 100

• 1 ≤ Ai ≤ Bi ≤ 1000

• 所有输入均为int

Output

输出有多少个符合题意的x，然后换行

Sample Input

3
3 2 5
6 9 8

Sample Output

2

Hint

一、题目大意

求，第一个数组的最大值与第二个数组的最小值之间有多少个数

二、思路

1、储备知识

a.求数组最大值的函数与数组最小值的函数

注1：头文件：#include
注2：在这里求的是地址，所以如果要获取最大最小值记得在，函数前面加上*,对返回值地址取值

思路A:

就简单粗暴求第一个数组最大值，与第二个数组的最小值，然后判断一下看中间是否有‘芝士’，没有的话需要特判为0.有的话就输出‘芝士’。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    //1.声明部分
    int n;
    int size;
    cin>>size;
    int *arr=new int[size]; //动态分配内存
    int *brr=new int[size];

    //2、输入
    for(int i=0;i<size;i++)cin>>arr[i];
    for(int i=0;i<size;i++)cin>>brr[i];

    //3、处理
    int maxArr=*max_element(arr,arr+size);//求数组arr的最大值
    int minBrr=*min_element(brr,brr+size);//求数组brr的最小值

    //4、输出
    if(maxArr>minBrr)cout<<0<<endl;
    else cout<<minBrr-maxArr+1<<endl;
    return 0;
}

思路B

不使用函数，就边输入边获取数组最大最小值，这样的空间与时间是最优的，时间复杂度达到O(n)

#include<iostream>
using namespace std;
int main()
{
    //1.声明部分
    int n ,num,miNum=1111,mxNum=-1;//注这里的最大值与最小值初始化在输入的边界外都行。
    cin>>n;

    //2、输入
    for(int i=0;i<n;i++)
    {
        cin>>num;
        if(mxNum<num)mxNum=num;
    }
    for(int i=0;i<n;i++)
    {
        cin>>num;
        if(miNum>num)miNum=num;
    }

    //4、输出
    if(mxNum>miNum)cout<<0<<endl;//特判没有芝士的情况
    else cout<<miNum-mxNum+1<<endl;
    return 0;
}