20190810贝壳找房开发岗笔试题讨论（全AC）

这套题，注意数据范围较大的情况，要用 long long 。。。

第一题：求绝对值最小，循环一遍判断即可，签到题，（AC）

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int T,n,m,sum,ans;
int main()
{
    //freopen("in.txt","r",stdin);
    cin >> n;
    vector<LL> num(n+1);
    for(int i = 0; i < n; ++i)
    {
        long long x;
        scanf("%lld",&x);
        num[i]= x;
    }
    LL t = abs(num[n-2] - num[n-1]);
    LL t1 = 0, t2 = 0;
    for(int i = 0; i < n-1; ++i)
    {
        LL tmp = abs(num[i] - num[i+1]);
        if(tmp < t)
        {
            t = tmp;
            t1 = num[i];
            t2 = num[i+1];
        }
    }
    cout<<t1<<" "<<t2<<endl;
    return 0;
}

第二题：最长递增子序列（ AC）

参考代码

//最长递增上升子序列
//思路：如果a[i]>tmp[len],tmp[++len] = a[i];否则从tmp[]中找到一个下界x,然后更新长度；复杂度O(NlogN) 
//LIS 是 计算最长递增子序列的长度,计算 tmp 数组的元素,array[]循环完一遍后,tmp 的长度 len 即为所求
//search 是修改的二分查找算法，返回数组元素需要插入的位置。   
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+233;
int T,n,m,sum,ans;
int a[maxn],maxLen[maxn];
int search(int L, int R, int num, int a[])
{
    int mid;
    while(L<=R)
    {
        mid = L+ (R-L)/2;
        if(a[mid]<=num)
            L =mid+1;
        else
            R = mid-1;
    }
    return L;
}
int LIS(int n)
{
    int *tmp = new int [n+1];
    int len =1;
    tmp[1]=a[1];
    for(int i=2; i<=n; ++i)
    {
        if(a[i]>tmp[len]) //如果大于 tmp 中最大的元素，则直接插入到 tmp 数组末尾
            tmp[++len]=a[i];
        else
        {
            int t = search(1,len,a[i],tmp);//二分查找需要插入的位置
            tmp[t]= a[i];
        }
    }
    return len;
    delete tmp;
}
int main()
{
    // freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i];
    }
    cout<<LIS(n)<<endl;
    return 0;
}

第三题：模拟题（AC ）

【思路】

//先排序，体重较大的减较小的，判断有没有体重较小值要大于等于较大值的90%

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+233;
const double eps = 1e-8;
int T,n,m,sum,ans;
int a[maxn];
int fun(int n)
{
    int ans = 0, L = 0, R = 0;
    while(L < n)
    {
        if(L == R)
        {
            ++R;
        }
        while ((R < n) && (a[R]*0.9 - a[L]*1.0 < eps))
        {
            ++R;
        }
        ans += (R - L -1);
        ++L;
    }
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=0; i<n; ++i)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    cout<<fun(n)<<endl;
    return 0;
}

第四题：贪心题可以过（AC）

【思路】：贪心，枚举中间的转折点，然后从左到右和从右到左依次更新花费；

如果当前元素比前一个元素小，那么贪心当前的最小花费就是比前一个元素大一；

同理从后面往前遍历也是如此，然后最后取最小值。

个人觉得是不是 DP 也可以做，但是没有好的思路。。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+233;
const double eps = 1e-8;
typedef long long LL;
int T,n,m,sum,ans;
LL a[maxn];
LL Lmax[maxn],Rmin[maxn];
LL Lsum[maxn],Rsum[maxn];
LL minCostIncThenDec(int n)
{
    Lmax[0] = a[0];
    Lsum[0] = 0;
    for(int i=1; i<n; ++i)
    {
        Lmax[i] = max(Lmax[i-1]+1, a[i]);
        Lsum[i] = Lsum[i-1] + Lmax[i] - a[i];
    }
    Rmin[n-1] = a[n-1];
    Rsum[n-1] = 0;

    for(int i=n-2; i>=0; --i)
    {
        Rmin[i] = max(Rmin[i+1]+1, a[i]);
        Rsum[i] = Rsum[i+1] + Rmin[i] - a[i];
    }
    LL ans = (1LL)*INT_MAX;
    LL tmp;
    for (int i=0; i<n; ++i)
    {
        if (Lmax[i] > Rmin[i])
        {
            tmp = Lsum[i] + Rsum[i] - Rmin[i] + a[i];
        }
        else if (Lmax[i] < Rmin[i])
        {
            tmp = Lsum[i] + Rsum[i] - Lmax[i] + a[i];
        }
        else
        {
            tmp = Lsum[i] + Rsum[i] - Lmax[i] + a[i];
        }
        ans = min(ans, tmp);
    }
    return ans;
}
void input()
{
    //freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=0; i<n; ++i)
    {
        cin>>a[i];
    }
}
void solve()
{
    cout<<minCostIncThenDec(n)<<endl;
}
int main()
{
    input();
    solve();
    return 0;
}

#贝壳找房##笔试题目#