蘑菇街2016校招算法题

朱雀 2022-07-28 09:14 187阅读 0赞

Arthur最近搬到了新的别墅，别墅特别大，原先的桌子显得比较小，所以他决定换一张新的桌子。他买了一张特别大的桌子，桌子是由很多条桌腿进行支撑的，可是回到家之后他发现桌子不稳，原来是桌子腿长度不太相同。他想要自己把桌子修理好，所以他决定移除掉一些桌腿来让桌子变得平稳。桌子腿总共有n条腿，第i条腿长度为li，Arthur移除第i桌腿要花费代价为di。假设k条腿桌子平稳的条件:超过一半桌腿能够达到桌腿长度的最大值。例如：一条腿的桌子是平稳的，两条腿的桌子腿一样长时是平稳的。请你帮Arthur计算一下是桌子变平稳的最小总代价。

##### 输入描述: #####

输入:
        第一行数据是一个整数：n (1≤n≤105)，n表示桌腿总数。
        第二行数据是n个整数：l1, l2, ..., ln (1≤li≤105)，表示每条桌腿的长度。
        第三行数据是n个整数：d1, d2, ..., dn (1≤di≤200)，表示移除每条桌腿的代价。

##### 输出描述: #####

输出:
        输出让桌子变平稳的最小总代价

##### 输入例子: #####

样例输入
    
        6
    
        2 2 1 1 3 3
    
        4 3 5 5 2 1

##### 输出例子: #####

思路：将桌腿按长度装进map里，map按从大到小顺序，从最长的桌腿·开始，以该长度的桌腿作为支撑桌腿，那么比他长的桌腿都要去掉，计算代价，再看看还需砍掉多少，从比该长度桌腿短的桌腿里选取代价最小的那些数量的桌腿砍掉，计算代价，计算总代价，更新最小代价。遍历直到最短长度桌腿。

本地测试的

void mincost(map<int, vector<int>, greater<int>>&hc,int &minc,int &n,int&precost)
    {
    	map<int, vector<int>, greater<int>>::iterator itt = hc.begin(); itt++;
    	vector<int>bb;
    	for (map<int, vector<int>, greater<int>>::iterator it = itt; it != hc.end(); it++)
    		for (int i = 0; i<it->second.size(); i++)
    			bb.push_back(it->second[i]);
    	sort(bb.begin(), bb.end());
    	int cost1 = 0;
    	for (int i = 0; !bb.empty()&&i < (n - (2 * (hc.begin()->second.size()) - 1)); i++)
    		cost1 += bb[i];
    	int cost2 = 0;
    	for (int i = 0; i<hc.begin()->second.size(); i++)
    		cost2 += hc.begin()->second[i];
    	if (cost1+precost<minc)
    		minc = cost1+precost;
    	n -= hc.begin()->second.size();
    	hc.erase(hc.begin());
    	precost += cost2;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int heigh[84] = { 49, 43, 46, 45, 36, 35, 34, 34, 41, 43, 35, 52, 44, 42, 37, 40, 52, 52, 48,
    		44, 49, 46, 52, 40, 44, 48, 35, 35, 41, 51, 44, 48, 38, 34, 43, 45, 42, 52, 50, 43, 53, 42, 34,
    		52, 38, 51, 42, 45, 34, 37, 44, 36, 44, 46, 48, 51, 34, 37, 45, 50, 53, 51, 44, 37, 53, 46, 47,
    		48, 50, 42, 43, 42, 45, 47, 42, 48, 50, 45, 50, 50, 34, 37, 40, 35
    	};
    	int cos[84] = { 155, 23, 96, 143, 100, 76, 112, 15, 137, 153, 75, 20, 29, 34, 78, 195,
    		64, 123, 44, 192, 109, 59, 62, 187, 75, 162, 146, 88, 126, 193, 100, 72, 166, 90, 75, 61,
    		95, 132, 26, 89, 42, 14, 141, 22, 7, 197, 76, 46, 85, 31, 199, 178, 180, 170, 179, 149,
    		36, 57, 68, 136, 166, 101, 96, 187, 109, 130, 155, 61, 106, 66, 125, 177, 30, 146, 39,
    		5, 168, 100, 100, 8, 170, 45, 157, 146 };
    	int hh[] = { 2, 2, 1, 1, 3, 3 };
    	int cc[] = { 4, 3, 5, 5, 2, 1 };
    	vector<int>hei(hh, hh + 6);
    	vector<int>co(cc, cc + 6);
    	int n = 6;
    	map<int, vector<int>, greater<int>>hc;
    	for (int i = 0; i<n; i++)
    		hc[hei[i]].push_back(co[i]);
    	if (hc.begin()->second.size() <= n / 2)
    	{
    		int minc = 10000000;
    		int precost = 0;
    		int k = n;
    		while (!hc.empty())
    			mincost(hc, minc, k, precost);
    		cout << minc;
    	}
    	else
    		cout << 0;
    	system("pause");
    	return 0;
    }

在线提交的

#include<vector>  
    #include<map>  
    #include<set>  
    #include<functional>  
    #include<deque>  
    #include<algorithm>  
    #include<iostream>  
    #include<stack>  
    #include<unordered_set>  
    #include<iterator>  
    #include<time.h>  
    #include<fstream>  
      
    using namespace std;  
      
    void mincost(map<int, vector<int>, greater<int>>&hc,int &minc,int &n,int&precost)  
    {  
        map<int, vector<int>, greater<int>>::iterator itt = hc.begin(); itt++;  
        vector<int>bb;  
        for (map<int, vector<int>, greater<int>>::iterator it = itt; it != hc.end(); it++)  
            for (int i = 0; i<it->second.size(); i++)  
                bb.push_back(it->second[i]);  
        if(!bb.empty())  
            sort(bb.begin(), bb.end());  
        int cost1 = 0;  
        if(!bb.empty())  
        for (int i = 0; i < (n - (2 * (hc.begin()->second.size()) - 1)); i++)  
            cost1 += bb[i];  
        int cost2 = 0;  
        for (int i = 0; i<hc.begin()->second.size(); i++)  
            cost2 += hc.begin()->second[i];  
        if (cost1+precost<minc)  
            minc = cost1+precost;  
        n -= hc.begin()->second.size();  
        hc.erase(hc.begin());  
        precost += cost2;  
    }  
      
       
    int main()  
    {  
        int n = 0;  
        int *legLen = NULL;  
        int *legVal = NULL;  
        
       
        while (cin >> n) {  
            legLen = new int[n];  
            legVal = new int[n];  
             
            for (int i = 0;i < n;++i)  
                cin >> legLen[i];  
            for (int i = 0;i < n;++i)  
                cin >> legVal[i];  
       
        map<int, vector<int>, greater<int>>hc;  
        for (int i = 0; i<n; i++)  
            hc[legLen[i]].push_back(legVal[i]);  
        if (hc.begin()->second.size() <= n / 2)  
        {  
            int minc = 10000000;  
            int precost = 0;  
            int k = n;  
            while (!hc.empty())  
                mincost(hc, minc, k, precost);  
            cout << minc;  
        }  
        else  
            cout << 0;  
              
       
            delete[] legLen;  
            delete[] legVal;  
         
        }  
       
        return 0;  
    }

真心对输入输出很不熟悉，在线写代码也很不习惯。莫名其妙出现您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起

但在vs2013上是没问题的，麻痹的。

测试用例:  
84  
49 43 46 45 36 35 34 34 41 43 35 52 44 42 37 40 52 52 48 44 49 46 52 40 44 48 35 35 41 51 44 48 38 34 43 45 42 52 50 43 53 42 34 52 38 51 42 45 34 37 44 36 44 46 48 51 34 37 45 50 53 51 44 37 53 46 47 48 50 42 43 42 45 47 42 48 50 45 50 50 34 37 40 35   
155 23 96 143 100 76 112 15 137 153 75 20 29 34 78 195 64 123 44 192 109 59 62 187 75 162 146 88 126 193 100 72 166 90 75 61 95 132 26 89 42 14 141 22 7 197 76 46 85 31 199 178 180 170 179 149 36 57 68 136 166 101 96 187 109 130 155 61 106 66 125 177 30 146 39 5 168 100 100 8 170 45 157 146   
  
对应输出应该为:  
  
6618