360 2018秋招笔试题

360 2018秋招笔试题

（后面再更新代码…）

1、卖粉笔

小明有m根彩色粉笔和n根白色粉笔，其中a根彩色粉笔和b根白色粉笔可以卖x元，c根白色粉笔可以卖y元，d根彩色铅笔可以卖z元，粉笔不一定要卖完，如何使利益最大？

举例：

输入：
m=5, n=5, a=1, b=2, c=3, d=3, x=2, y=1, z=3,
输出：
7

解析：

递归搜索。共有三种卖的方式：
[a , b] —> x
[0, c] —> y
[d, 0] —> z
每次都从这三种方式中选择一个利益最多的方式，剩下的粉笔继续递归搜索，直至卖完或者卖不出去了。

c++代码实现：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int sell(vector<int>& objects,vector<vector<int>>& special,map<vector<int>,int>& answer)
{
    if(answer.find(objects)!=answer.end())
        return answer[objects];
    int result = 0, j = 0;
    for(vector<int> s : special) {
        vector<int> rest(objects.begin(),objects.end());
        for( j=0; j<objects.size(); j++) {
            int diff = rest[j]-s[j];
            if(diff<0)
                break;
            rest[j] = diff;
        }
        if(j==objects.size()) {
            int money = s[j] + sell(rest,special,answer);
            result = money > result ? money : result;
        }
    }
    answer[objects] = result;
    //没卖完的，返回0
    return result;
}

int shoppingOffer(vector<int>& objects,vector<vector<int>>& special)
{
    map<vector<int>,int> answer;
    return sell(objects,special,answer);
}

int main()
{
    int m,n,a,b,c,d,x,y,z;
    cin>>m>>n>>a>>b>>c>>d>>x>>y>>z;
    vector<vector<int>> special = {{a,b,x},{0,c,y},{d,0,z}};
    vector<int> objects = {m,n};
    cout<<shoppingOffer(objects,special)<<endl;
    return 0;
}

---

2、数组交换

有两个数组，分别是a[a1, a2, …, an]和b[b1, b2, …, bm]，sum表示数组所有的元素和，最多交换a和b数组中两对数字，使得；两个交换后的的数组的sum的差值的绝对值最小？

举例：

输入：
n=4, a= [1, 3, 7, 9], m=3, b=[2, 10, 12]
输出：
0
解释：交换（3，2）和（9，12）两对，最后两个数组的元素和都为22。差值的绝对值即为0。

解析：

先来看这个问题，交换两个数组的某对元素，使得两个数组的元素和差值的绝对值最小，这个问题比上面的问题少了一个限制：元素的交换次数不限制。
数组a，元素和记为sumA；数组b，元素和记为sumB。
如果sumA==sumB，则不用交换。
不失一般性的，我们假设sumA > sumB，delta = sumA-sumB。
假设a[i]与b[j]交换，则：sumA’=sumA-a[i]+b[j], sumB’=sumB-b[j]+a[i]
delta’ = sumA’-sumB’ = delta - 2*(a[i]-b[j])。
因此，要使得两个数组元素和尽可能相等，则delta’尽可能等于0，应使a[i]-b[j]尽可能接近delta/2。
但是本题有限制，最多交换两次。目前方法还没想出来。

C++代码实现：
交换两个数组的某对元素，使得两个数组的元素和差值的绝对值最小

#include <iostream>
#include <math.h>
using namespace std;

int change(int a[],int n,int b[],int m,int sumA,int sumB)
{
    int delta = 0;
    bool bigger = true;
    if(sumA>sumB){
        delta = sumA - sumB;
        bigger = true;
    }
    else{
        delta = sumB - sumA;
        bigger = false;
    }
    int diff = 0, x=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            diff = a[i]-b[j];
            x = diff > 0 ? diff : (~diff+1); //abs(diff)
            if((x*2 <= delta)&&((bigger && diff>0)||(!bigger && diff<0))){
               a[i] ^= b[i];
               b[i] = a[i]^b[i];
               a[i] = a[i]^b[i];   //交换a[i] b[j]
               delta -= 2*x;
               if(delta==0)
                    return 0;
            }
        }
    }
    return delta;
}

int main()
{
    int n,m,sumA=0,sumB=0;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
        sumA += a[i];
    }

    cin>>m;
    int b[m];
    for(int i=0; i<m; i++){
        cin>>b[i];
        sumB += b[i];
    }
    if(sumA==sumB)
        cout<<0;
    else
        cout<<change(a,n,b,m,sumA,sumB);
    return 0;
}

---