首页 > 试题广场 >

修理桌子

[编程题]修理桌子
  • 热度指数:949 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
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),表示移除每条桌腿的代价。


输出描述:
输出:
    输出让桌子变平稳的最小总代价
示例1

输入

样例输入<br />
    6<br />
    2 2 1 1 3 3<br />
    4 3 5 5 2 1<br />

输出

8
以题目中的例子说明算法:
2 2 1 1 3 3
4 3 5 5 2 1
首先,按桌腿长度由大到小排序
3 3 2 2 1 1
2 1 4 3 5 5
统计最长桌腿数m(这里m=2),若m*2>n(n为桌腿总数,这里n=6),则符合要求,不用砍桌腿,否则,有两种决策:
a.不砍这些桌腿,保留它们,“成全”答案,即在剩下的n-m条桌腿中保留代价最大的m-1条,砍掉其余的n-m-(m-1)=n-m-m+1条代价最小的桌腿。
b.砍掉这些最长的桌腿,但剩下的桌腿是否满足要求还不一定,需要重做上述步骤。
       我们发现,方案a一定可以让桌子平稳,但是,我们无法保证这样做的代价是最小的,因为如果我们砍掉这些最长桌腿,由剩余桌腿构造出的解的代价(当然要加上这些已经砍掉的最长桌腿的代价)可能更小。所以,我们需要假设砍掉了这些最长桌腿,然后观察剩余桌腿,如果他们还不能使桌子平稳,还得继续进行a,b决策,知道我们发现,当前剩余桌腿能够使桌子平稳了。(当然,在这种情况下,如果我们继续砍桌腿,还可能出现新的解,但这些解是在已有解的基础上再砍桌腿造成的,成本必然增加,所以,只要我们明确已经“砍出”一个解了,就不必再继续算下去了)
对于上例,我们先砍掉最长的桌腿,代价delete_cost=2+1=3,同时,更新桌腿总数n=n-m=6-2=4。
然后,对剩余桌腿按照代价由小到大排序,如下
2 2 1 1
3 4 5 5
然后统计前n-m+1(由于前面已经更新了总桌腿数n,所以这里是n-m+1而不是n-m-m+1)条桌腿的代价result_cost=3+4+5=12
这个result_cost对应的就是答案
1 3 3
5 2 1
的代价,即我们前边说的保留桌腿,“成全”答案的代价。
我们发现,无论是否保留最长桌腿,在实际编程时,都可以“真的”砍掉最长桌腿,因为计算保留它们,“成全”答案的这种情况的代价时,并不需要最长桌腿的代价。
这里,我们记着将result_cost与min_cost(min_cost初始化为一个很大的数,如1000000)相比较,若result_cost<min_cost,则执行min_cost=result_cost刷新min_cost,以保证min_cost保存的是当前的最小代价。这里,min_cost被更新为12。
接着,对砍掉最长桌腿的剩余桌腿再按照桌腿长度由大到小排序,如下
2 2 1 1
3 4 5 5
此时,m=2,n=4,m*2>n仍然不满足,于是再将2 2砍掉,delete_cost=3+3+4=10(第一个3是上次砍掉3 3时的代价,注意,delete_cost需要累加上次的delete_cost,因为本次砍桌腿是在砍掉前边那些桌腿的基础上砍的),然后更新n,n=n-m=4-2=2
然后,再将剩余桌腿按照代价由小到大排序,有
1 1
5 5
再计算前n-m+1=2-2+1=1条桌腿的代价,result_cost=3+5=8,注意,砍掉1这条桌腿,是在上一轮砍掉3 3这两条桌腿上做的,所以,
result_cost也要累加上次的delete_cost。这里,result_cost=8对应的答案是:砍掉
3 3 1
2 1 5
剩下
2 2 1 <-----------------------------------------这就是当前答案
3 4 5
的情况。
由于8<12,所以将min_cost更新为8。
接着,对砍掉最长桌腿的剩余桌腿再按照桌腿长度由大到小排序,如下
1 1
5 5
此时,m=2,n=2,满足m*2>n,所以
1 1
5 5
也是一个答案,它对应的代价就是当前已经砍掉的所有的桌腿的代价,就是当前的delete_cost值,这里就是10。
因为条件m*2>n已经满足,所以不需要继续往下算了。
此时,一共有两个代价,一个是所有“保留长腿,成全答案”的情况中的最小代价,就是nim_cost的值,另一个是依次砍掉最长桌腿,直到出现满足要求的解的代价,就是delete_cost的值,所以,我们最后比较这两个值,输出小者,程序结束。
本例中,min_cost=8,delete_cost=10,所以我们输出8,这就是代价最小的解,它对应的情况是:砍掉
3 3 1
2 1 5
剩下
2 2 1
3 4 5
的情况。

下面给出具体算法:
a.初始化:int del_cost = 0, res_cost = 0, min_cost = 10000000;;
b.将桌腿按长度由大到小排序,统计最长桌腿数m,若m*2>n,输出min_cost和del_cost中的小者,否则,令tempcost=del_cost;
   del_cost=del_cost+m个最长桌腿数的代价;n=n-m;;
c.对除去最长桌腿的剩余桌腿按代价由小到大排序,统计前n-m+1个代价的和summincost,令res_cost=temp+summincost;,若res_cost<min_cost,则min_cost=res_cost;,最后,返回到步骤b。

最后,给出具体实现代码:
#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Leg
{
	int len;
	int cost;
	Leg(int _len, int _cost)
	{
		len = _len;
		cost = _cost;
	}
};

bool comlen(Leg legi, Leg legj)
{
	return (legi.len > legj.len);
}
bool comcost(Leg legi, Leg legj)
{
	return (legi.cost < legj.cost);
}

int main(void)
{
	vector<Leg> someleg;
	vector<int>saveid;
	vector<int> ltemp;
	vector<int> ctemp;
	int n;
	while (cin >> n)
	{
		for (int i = 0; i < n; i++)//输入桌腿长度
		{
			int a;
			cin >> a;
			ltemp.push_back(a);
		}
		for (int i = 0; i < n; i++)//输入拆桌腿的代价
		{
			int b;
			cin >> b;
			ctemp.push_back(b);
		}
		for (auto it = ltemp.begin(), itt = ctemp.begin(); it != ltemp.end() && itt != ctemp.end(); ++it, ++itt)//构造桌腿结构体
		{
			Leg leg(*it, *itt);
			someleg.push_back(leg);
		}
		int del_cost = 0, res_cost = 0, min_cost = 10000000;
		while (true)
		{
			std::sort(someleg.begin(), someleg.end(), comlen);//按桌腿长度从大到小排序
			int m = 0;
			int tlen = someleg[0].len;
			for (auto it = someleg.begin(); it != someleg.end(); ++it)//找出最大长度的桌腿的个数
			{
				if (tlen == it->len)
				{
					++m;
				}
				else
				{
					break;
				}
			}
			if (m * 2 > n)
			{
				int mincost = del_cost < min_cost ? del_cost : min_cost;
				cout << mincost << endl;
				break;
			}
			else
			{
				int tempcost = del_cost;
				int tcost = 0;
				for (int i = 0; i < m; i++)//计算出拆除最大长度的桌腿的代价
				{
					tcost += someleg[i].cost;
				}
				del_cost += tcost;
				someleg.erase(someleg.begin(), someleg.begin() + m);//拆掉最长桌腿
				n -= m;
				std::sort(someleg.begin(), someleg.end(), comcost);//剩余桌腿按代价由小到大排序
				int summincost = 0;

				for (int i = 0; i < n - m + 1; i++)//如果保留那cnt个最长的桌腿,就必须拆除n-cnt-(cnt-1)个短桌腿,由于前边已经有了n-=cnt,所以
				{                                //这里只需n-cnt+1,为保证代价最小,必须拆除代价最小的n-cnt+1条桌腿
					summincost += someleg[i].cost;
				}
				res_cost = summincost + tempcost;
				if (res_cost < min_cost)
				{
					min_cost = res_cost;
				}
			}
		}
	}
	return 0;
}


发表于 2016-04-21 10:15:54 回复(4)
大体思路是把先把输入的腿长映射到一个106维的腿长数目数组,数组中的值为对应腿长的的数目。然后从后往前遍历
没碰到一个腿长,将比他高的腿长砍掉,同时计算还需要砍多少桌腿,对剩余的桌腿排序砍掉对应部分,然后计算最小值。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        vector<int >l,d,d_cut;
        int a[106]={0};
        int li,di;
        for(int i=0;i<n;i++)
        {
            cin>>li;
            l.push_back(li);
            a[li]++;
        }
        int minCost=0;
        for(int i=0;i<n;i++)
        {
            cin>>di;
            d.push_back(di);
            minCost+=di;
        }
        for(int i=105;i>0;i--)
        {
            int cost=0; 
            d_cut.clear();
            if(a[i])
            {
                int cutLegNum=l.size()-a[i];
                for(int j=i+1;j<=105;j++)
                {
                    cutLegNum-=a[j];
                }
                cutLegNum-=(a[i]-1);
                for(int k=0;k<n;k++)
                {
                    if(l[k]<i)
                        d_cut.push_back(d[k]);
                    if(l[k]>i)
                        cost+=d[k];
                }
                if(cutLegNum>0)
                {
                    sort(d_cut.begin(),d_cut.end()); 
		    for (int k = 0; k <cutLegNum; k++)
                        cost+=d_cut[k];
                    if(cost<minCost)
                        minCost=cost;
                }      
            }
        }
        cout<<minCost<<endl;
    }
    return 0;  
}

发表于 2016-04-12 11:43:30 回复(2)
个人思路:另外增加一个数组用于保存已排序的腿长数组A,从最长腿至最短腿遍历计算代价值,计算分一下步骤:
1.指定腿长len
2.查找指定腿长在已排序数组中的两端位置(有重复腿长)
3.确定小于该腿长的桌腿应除去的数量即:n=2*front-back(可以画个图自己算一下------****-------)
4.把小于len的腿长排序,取前n个将代价累加到sum
5.把大于len的腿长代价累加sum,得到一次计算的结果
抛砖引玉,自己写得比较繁琐,图省事也没处理重复腿长计算              
#include "iostream"
#include "algorithm"
#include "vector"
using namespace std;
int num;
int findBack(int *arr,int id){
    for(int i=num-1;i>=0;i--){
        if(arr[i]==id)return i;
    }
    return -1;
}
int findFront(int *arr,int id){
    for(int i=0;i<num;i++){
        if(arr[i]==id)return i;
    }
    return -1;
}
int calMin(int *pL,int *pD,int *pS,int i){
    if(i==1)return -1;
    int len=pS[i];
    int back=findBack(pS,len);
    int front=findFront(pS,len);
    int rmvElse=2*front-back; //
    
    vector<int> vec;
    for(int i=0;i<num;i++){
        if(pL[i]<len){
            vec.push_back(pD[i]);
        }
    }
    sort(vec.begin(),vec.end());    //sort
    int sum=0;
    for(int i=0;i<rmvElse;i++){
        sum=sum+vec[i];
    }
    for(int i=0;i<num;i++){
        if(pL[i]>len)sum+=pD[i];
    }
    return sum;
}
int findMin(int *pL,int *pD,int *pS){
    int i=num-1;
    int min=100000;
    while(1){
        int res=calMin(pL,pD,pS,i);
        //cout<<res<<" ";
        if(res==-1)break;
        if(res<min)min=res;
        i--;
    }
    return min;
}
int main(){
    cin>>num;
    int pL[num],pD[num],pS[num];
    for(int i=0;i<num;i++){
        cin>>pL[i];
        pS[i]=pL[i];
    }
    for(int i=0;i<num;i++)cin>>pD[i];
    sort(pS,pS+num);
    int ans=findMin(pL,pD,pS);
    cout<<ans<<endl;
    return 0;
}
发表于 2016-04-10 19:36:37 回复(0)
#--coding:utf-8--
class Deskleg(object):
    def __init__(self,li,di):
        self.li,self.di=li,di
 
#根据di、li由小到大排序的比较函数
def sort_di(x,y):
    return x.di-y.di
def sort_li(x,y):
    return x.li-y.li
#主函数
def Solution():
    nums=int(raw_input())
    _li=raw_input().split()
    _di=raw_input().split()
    ans=[]#存储可能出现的所有代价
    list_a=[]#存储所有桌腿数据
    for i in range(nums):
        list_a.append(Deskleg(int(_li[i]),int(_di[i])))
    list_a.sort(sort_li)
    list_b=[]#二维列表,li、di由小到大排列
    count=1
    temp=[list_a[0]]
    while count<nums:
        if list_a[count].li==list_a[count-1].li:
            temp.append(list_a[count])
        else:
            list_b.append(temp)
            temp=[list_a[count]]
        count+=1
    list_b.append(temp)
    for i in list_b:
        i.sort(sort_di)
    #开始求解
    for i in range(len(list_b)):
        a_ans=0
        l1=len(list_b[i])#最长桌腿数
        l2=0#存储比最长桌腿短的桌腿数
        for j in range(i+1,len(list_b)):
            for k in list_b[j]:
                a_ans+=k.di
        temp_1=[]
        if i>0:
            for j in range(0,i):
                for k in list_b[j]:
                    temp_1.append(k)
            l2=len(temp_1)
            temp_1.sort(sort_di)
        if l2>=l1:
            for m in range(l2-l1+1):
                a_ans+=temp_1[m].di
        ans.append(a_ans)
    return min(ans)
print Solution()

发表于 2016-04-12 10:43:36 回复(0)
自己独立完成了,提交通过了看看发现思路和一楼的思路一样,就不解释了
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
  int cnt, i, l, n, cost, minCost;
  set<int> s;
  vector<int> v;
  scanf("%d", &n);
  int length[n], value[n];
  for (i=0; i<n; ++i) {
    scanf("%d", &length[i]);
    s.insert(length[i]);
  }
  for (i=0; i<n; ++i)
    scanf("%d", &value[i]);
  minCost = 0x7fffffff;
  for (auto it=s.begin(); it!=s.end(); ++it) {
    l = *it;
    cnt = cost = 0;
    v.clear();
    for (i=0; i<n; ++i) {
      if (length[i] == l)
        cnt++;
      else if (length[i] > l)
        cost += value[i];
      else v.push_back(value[i]);
    }
    if (v.size())
      sort(v.begin(), v.end());
    if (v.size() > cnt-1)
      for (i=0; i<v.size()-cnt+1; ++i)
        cost += v[i];
    minCost = min(minCost, cost);
  }
  printf("%d\n", minCost);
  return 0;
}

编辑于 2018-02-26 22:20:28 回复(0)
这道题和动态规划有关系吗
发表于 2017-09-04 00:40:48 回复(0)
//VS调试中正确,放在网页里不对
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
struct leg
{
	int count = 0;
	int total = 0;
	vector<int> costs;
};
map<int, leg> table;
typedef map<int, leg>::iterator miterator;

int calculate(miterator it, int n, int cost);
int main()
{
	int n, temp;
	//进行数据输入
	cin >> n;
	vector<pair<int, int> > legs(n, pair<int, int>(0, 0));
	for (int i = 0; i<n; i++)
	{
		cin >> temp;
		legs[i].first = temp;
	}
	for (int i = 0; i<n; i++)
	{
		cin >> temp;
		legs[i].second = temp;
	}
	//进行数据整合
	for (int i = 0; i<legs.size(); i++)
	{
		int len = legs[i].first;
		table[len].count++;
		table[len].total += legs[i].second;
		table[len].costs.push_back(legs[i].second);
	}
	//进行数据处理
	miterator iter = --table.end();
	int result = calculate(iter, n, 0);
	cout << result << endl;
	return 0;
}
//建立计算函数
int calculate(miterator it, int n, int cost)
{
	if (it->second.count * 2>n)
		return cost;
	//递归算法
	//去掉当前最大长度的桌子
	int result1 = calculate(--it, n - it->second.count, cost + it->second.total);
	//保留当前最大长度桌子
	++it;
	int result2 = cost;
	int k = n - 2 * it->second.count + 1;
	priority_queue<int> dearr;
	for (miterator p = table.begin(); p != it; p++)
		for (int i = 0; i<p->second.costs.size(); i++)
			if (dearr.size()<k)
				dearr.push(p->second.costs[i]);
			else if (dearr.top()>p->second.costs[i])
			{
				dearr.pop();
				dearr.push(p->second.costs[i]);
			}
	while (dearr.size() != 0)
	{
		result2 += dearr.top();
		dearr.pop();
	}
	int result = result1<result2 ? result1 : result2;
	return result;
}

发表于 2017-08-31 21:11:55 回复(0)
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] li = new int[n];
        for(int i=0; i<n; i++){
            li[i] = scanner.nextInt();
        }
        int[] di = new int[n];
        for(int i=0; i<n; i++){
            di[i] = scanner.nextInt();
        }

        //按桌腿长度从大到小排序
        for(int i=0; i<n-1; i++){
            int index = i;
            for(int j=i+1; j<n; j++){
                if(li[j]>li[index]){
                    index = j;
                }
            }
            if(index!=i){
                int temp = li[i];
                li[i] = li[index];
                li[index] = temp;
                temp = di[i];
                di[i] = di[index];
                di[index] = temp;
            }
        }

        int result = getMin(li, di, 0, n);
        System.out.println(result);
    }

    //求最优解
    public static int getMin(int[] li, int[] di, int start, int n){

        int maxNum = 1;
        int count = di[start];
        for(int i=start+1; i<n; i++){
            if(li[i]==li[start]){
                maxNum++;
                count += di[i];
            }else{
                break;
            }
        }

        if(maxNum*2>n-start){
            return 0;
        }
        else{
            //不保留当前最长桌腿
            int a = getMin(li, di, start+maxNum, n) + count;
            //保留当前最长桌腿
            int b = getCount(li, di, start+maxNum, maxNum, n);
            return a<b?a:b;
        }
    }

    //保留最长桌腿,砍去其他代价和最小的部分桌腿s
    private static int getCount(int[] li, int[] di, int start, int maxNum, int n) {
        int num = n-start-maxNum;
        if(num<0){
            return 0;
        }else{
            int[] arr = new int[n-start];
            int length = arr.length;
            for(int i=0; i<arr.length; i++){
                arr[i]=di[start+i];
            }
            int count = 0;
            int x = 0;
            while(num>=0){
                int index=x;
                for(int i=x; i<length; i++){
                    if(arr[i]<arr[index]){
                        index=i;
                    }
                }
                int temp = arr[index];
                arr[index] = arr[x];
                arr[x] = temp;
                count += arr[x];
                x++;
                num--;
            }
            return count;
        }
    }
}

编辑于 2017-07-10 13:24:48 回复(0)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#define MM(a,b) memset(a,b,sizeof(a))
#define rf(a) scanf("%lf",&a)
#define ri(a) scanf("%d",&a)
#define PF printf
#define PB push_back
#define SC scanf
#define CT continue
typedef long long ll;
typedef unsigned long long ULL;
const double eps = 1e-14;
const int inf = 0x3f3f3f3f;
const int N=1e2+10;
const double pi=acos(-1);
using namespace std;

struct node{
   int l,d;
}ne[N];

bool cmpd(const node&a,const node &b)
{
   return a.d<b.d;
}


int main()
{
    int n;
    while(~ri(n)){
        for(int i=1;i<=n;i++)  ri(ne[i].l);
        for(int i=1;i<=n;i++)  ri(ne[i].d);
        int ans=inf;
        sort(ne+1,ne+n+1,cmpd);
        for(int i=1;i<=n;i++){
            int tmp=0,cut=0,equ=0;
            for(int j=1;j<=n;j++)
                if(ne[j].l>ne[i].l) tmp+=ne[j].d,cut++;
                else if(ne[j].l==ne[i].l) equ++;
            for(int j=1;j<=n&&equ<=(n-cut)/2;j++)
                if(ne[j].l<ne[i].l){
                cut++,tmp+=ne[j].d;
            }
            ans=min(ans,tmp);
        }
        PF("%d\n",ans);
    }
    return 0;
}


发表于 2017-05-04 11:33:19 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmpVec0(vector<int> c1,vector<int> c2){
    return c1[0]<c2[0];
}

bool cmpVec1(vector<int> c1,vector<int> c2){
    return c1[1]<c2[1];
}

int main(){
    int n=0;
    cin >> n;
    vector<vector<int>> nums(n);
    for (int i = 0; i < n; i++){
        int tmp=0;
        cin >> tmp;
        nums[i].push_back(tmp);
    }
    for (int i = 0; i < n; i++){
        int tmp=0;
        cin >> tmp;
        nums[i].push_back(tmp);
    }

    sort(nums.begin(),nums.end(),cmpVec0);

    int count=1;
    int min = 0x7fffffff;
    for (int i = n-1; i >0; i--)
    {
        if (nums[i][0]==nums[i-1][0])
        {
            count++;
            continue;
        }
        else
        {
            vector<vector<int>> tmpVec(nums);
            int cost = 0;
            //int remain = n-count;
            for (int j = i+count; j < n; j++)        cost += nums[j][1];
            int remain = i;
            if (i<count)
            {
                if (cost<min)    min = cost;
            }
            else{
                tmpVec.erase(tmpVec.begin()+i,tmpVec.end());
                sort(tmpVec.begin(),tmpVec.end(),cmpVec1);
                int toRemove = remain-count;
                for (int j = 0; j <= toRemove; j++)        cost += tmpVec[j][1];
                if (cost<min)    min = cost;
            }
            count=1;
        }
    }


    vector<vector<int>> tmpVec(nums);
    int cost = 0;
    for (int j = count; j < n; j++)        cost += nums[j][1];
    if (cost<min)    min = cost;

    cout << min << endl;

    //for (int i = 0; i < n; i++)        cout << nums[i][0] << " " << nums[i][1] << endl;

    //getchar();
    //getchar();
    return 0;
}
发表于 2016-09-30 14:11:24 回复(0)
感谢@好学上进的思路。我参考他的两点思路实现了一下代码:
a.不砍这些桌腿,保留它们,“成全”答案,即在剩下的n-m条桌腿中保留代价最大的m-1条,砍掉其余的n-m-(m-1)=n-m-m+1条代价最小的桌腿。
b.砍掉这些最长的桌腿,但剩下的桌腿是否满足要求还不一定,需要重做上述步骤。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] ln = new int[n];
            int[] dn = new int[n];
            for (int i = 0; i < n; i++) {
                ln[i] = in.nextInt();
            }
            for (int i = 0; i < n; i++) {
                dn[i] = in.nextInt();
            }
            int min = count(ln, dn);
            System.out.println(min);
        }
    }
    
    private static int count(int[] ln, int[] dn) {
        List<Node> list = new ArrayList<>();
        for (int i = 0; i < ln.length; i++) {
            list.add(new Node(ln[i], dn[i]));
        }

        return count(list);
    }

    private static int count(List<Node> list) {
        List<Node> max = new ArrayList<>();
        if (list == null || list.size() == 0 || isStable(list, max)) {
            return 0;
        }

        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost < o2.cost ? 1 : -1;
            }
        });
        int cost1 = 0;
        for (int i = max.size() - 1; i < list.size(); i++) {
            cost1 += list.get(i).cost;
        }
        int cost2 = 0;
        for (int i = 0; i < max.size(); i++) {
            cost2 += max.get(i).cost;
        }

        return Math.min(cost1, cost2 + count(list));
    }

    /**
     * 判断桌子当前是否稳定
     *
     * @param list
     * @return
     */
    private static boolean isStable(List<Node> list, List<Node> max) {
        int maxLen = 0;
        for (int i = 0; i < list.size(); i++) {
            maxLen = maxLen < list.get(i).length ? list.get(i).length : maxLen;
        }
        int m = 0;
        max.clear();
        for (int i = 0; i < list.size(); i++) {
            if (maxLen == list.get(i).length) {
                m++;
                max.add(list.get(i));
            }
        }
        for (int i = 0; i < max.size(); i++) {
            list.remove(max.get(i));
        }

        return m * 2 > (list.size() + max.size());
    }

    static class Node {
        public int length;
        public int cost;

        public Node(int length, int cost) {
            this.length = length;
            this.cost = cost;
        }
    }
}

发表于 2016-09-22 21:23:57 回复(0)
#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[])
{
    int n;
    while (cin >> n) {
        vector<int> len, val;
        // 表示某一个长度的桌腿出现的次数
        unordered_map<int, int> ump;
        len .resize(n), val.resize(n);
        for (int i = 0; i < n; ++i) {
            cin >> len[i];
            ++ump[len[i]];
        }
        for (int i = 0; i < n; ++i) {
            cin >> val[i];
        }
        // input finished
        int ret = INT_MAX;
        for (auto &ele:ump) {
            // 以var为最终的桌腿的标准
            int var = ele.first;
            // 表示代价
            int cost = 0;
            vector<pair<int, int> > mp;
            for (int i = 0; i < n; ++i) {
                // 凡是比var大的桌腿都割掉,比它小的加入一个集合
                if (len[i] > var) {
                    cost += val[i];//割掉
                } else if (len[i] < var) {
                    // 比var小的桌腿加入mp集合
                    mp.push_back({val[i], i});
                }
            }
            // 将集合里面的元素按照割掉的代价排序
            sort(mp.begin(), mp.end(), [](const pair<int,int> &p1, const pair<int, int> &p2)
            { return p1.first < p2.first;});
            // 长度为 var 总共的桌腿条数
            int sz_var = ump[var];
            // 比var小的桌腿条数
            int sz_mp = mp.size();
            // 割掉小的,留大的
            if (sz_mp < sz_var) {//无需割掉
                ret = min(ret, cost);
            } else {
                // 需要割掉的条数
                int cnt = sz_mp - sz_var + 1;
                // 肯定是mp割前面的
                for (auto it = mp.begin(); it != next(mp.begin(), cnt); ++it) {
                    cost += it->first;
                }
                ret = min(ret, cost);
            }
        }//for
        cout << ret << endl;
    }//while
    return 0;
}
没有啥套路,就是把逻辑理清楚就行。

发表于 2016-09-05 15:49:18 回复(0)
# coding=utf-8
"""
1. 比当前长度大的都要去除
2. 根据剩余中是否满足最大个数大于一般条件处理小于当前长度的值
"""
def solution(l_lst, c_lst, n):  # 输入 长度lst 和 代价lst
    all_len = set(l_lst)
    len_cast = zip(c_lst, l_lst)
    len_cast.sort()
    ret = []
    foreach_len in all_len:
        tmp_mx = []
        tmp_mi = []
        tmp_count = l_lst.count(each_len)
        fore in len_cast:
            ifeach_len < e[1]:
                tmp_mx.append(e[0])
            elif each_len > e[1]:
                tmp_mi.append(e[0])
        iflen(tmp_mx) > n - 2*tmp_count:
            tmp_sum = sum(tmp_mx)
        else:
            tmp_mi.sort()
            tmp_sum = sum(tmp_mi[:1+n-2*tmp_count-len(tmp_mx)]) + sum(tmp_mx)
        ret.append(tmp_sum)
    returnmin(ret)
 
importsys
 
try:
    whileTrue:
        line = sys.stdin.readline().strip()
        ifnot line:
            break
        n = int(line)
        line_2 = sys.stdin.readline().strip().split()
        line_3 = sys.stdin.readline().strip().split()
        line_2 = map(int, line_2)
        line_3 = map(int, line_3)
        # len_cast = zip(line_2, line_3)
        print solution(line_2, line_3, n)
except:
    pass

发表于 2016-08-25 17:38:47 回复(0)
import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.List;import java.util.Map;import java.util.Scanner;import DataStructures.Comparable;public class TableQuestion { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); int[] a=new int[n]; int[] b=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); b[i]=sc.nextInt(); } System.out.println(minD(a,b)); } } /* * 求最小代价 */ public static int minD(int[] arr,int[] arr2){ Map<Integer,List<Integer>> mp=new HashMap<Integer,List<Integer>>(); for(int i=0;i<arr.length;i++){ if(!mp.containsKey(arr[i])){ List<Integer> lst=new ArrayList<Integer>(); mp.put(arr[i], lst); } mp.get(arr[i]).add(i); } Iterator<Integer> it = mp.keySet().iterator(); int arr3[]=new int[mp.keySet().size()]; int tmp0=0; while(it.hasNext()){ arr3[tmp0++]=it.next(); } shellsort(arr3); int[] sum=new int[arr3.length]; int all=0; for(int i=0;i<arr.length;i++){ all+=arr2[i]; } List<Integer> lst=new ArrayList<Integer>(); for(int j=arr3.length-1;j>=0;j--){ List<Integer> list=mp.get(arr3[j]); int[] arr5=new int[arr2.length-lst.size()]; //arr2的copy int j_sum=0; for(int k=0;k<list.size();k++){ j_sum+=arr2[list.get(k)];; lst.add(list.get(k)); } int tmp=0; for(int k=0;k<arr2.length;k++){ if(!lst.contains(k)) arr5[tmp++]=arr2[k]; } int other=0; if(arr5.length>list.size()-1) other= shellToSum(arr5,list.size()-1); sum[j]=all-j_sum-other; } return min(sum); } public static void shellsort( int[] arr3 ) { int j;/* 1*/ for( int gap = arr3.length / 2; gap > 0; gap /= 2 )/* 2*/ for( int i = gap; i < arr3.length; i++ ) {/* 3*/ Integer tmp = arr3[ i ];/* 4*/ for( j = i; j >= gap && tmp.compareTo( arr3[ j - gap ] ) < 0; j -= gap )/* 5*/ arr3[ j ] = arr3[ j - gap ];/* 6*/ arr3[ j ] = tmp; } } public static int shellToSum(int[] a,int size){ int[] b=a; shellsort(a); int sum=0; for(int i=0;i<size;i++){ sum+=b[b.length-1-i]; } return sum; } public static int min(int[] a){ int[] b=a; shellsort(b); return b[0]; }}
发表于 2016-08-08 17:38:29 回复(0)
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
 
intcal(map<int,vector<int>> &lc){
    map<int,vector<int>>::iterator itr=lc.begin();
    intsize=0;//所有数据的个数
    intmaxlen=0;//最长腿
    while(itr!=lc.end()){
        if(maxlen<itr->first){
            maxlen=itr->first;
        }
        size+=(itr->second).size();
        itr++;
    }
    intcurrsize=lc[maxlen].size();
    if(currsize>size/2)//如果最长退满足约束条件
        return0;
     
    vector<int> tmp;//存储所有短腿的代价值
    itr=lc.begin();
    while(itr!=lc.end()){
        if(itr->first!=maxlen){
            tmp.insert(tmp.end(),itr->second.begin(),itr->second.end());
        }       
        itr++;
    }
    sort(tmp.begin(),tmp.end());//按代价值升序排列
    intc2=0;//保留最长腿的代价
    while(!tmp.empty()&&currsize<=(currsize+tmp.size())/2){
        c2+=tmp.front();
        tmp.erase(tmp.begin());
    }
    intc1=0;//去掉最长退的代价
    for(inti=0;i<currsize;i++){
        c1+=lc[maxlen][i];
    }
    lc.erase(maxlen);
    c1+=cal(lc);
    returnc1<c2?c1:c2;
}
intmain(){
    intn;
    vector<int> L;
    vector<int> C;
     
    intl,c;
    while(cin>>n){
        L.clear();
        C.clear();
        for(inti=0;i<n;i++){
            cin>>l;
            L.push_back(l);
        }
        for(inti=0;i<n;i++){
            cin>>c;
            C.push_back(c);
        }
        map<int,vector<int>> lc;
         //构造map
        for(inti=0;i<n;i++){
            l=L[i];
            if(lc.find(l)==lc.end()){
                vector<int> v;
                v.push_back(C[i]);
                lc.insert(make_pair(l,v));
            }
            else{
                lc[l].push_back(C[i]);
            }
        }
        cout<<cal(lc)<<endl;
    }
    return0;
}
在所有的数值输入之后,设计一个map<int,vector<int>>,是一个长度值对应的所有的代价值;
如果在当前状态下,最长的腿占比例>1/2,代价为0;
否则,在计算代价时,需要分两种情况考虑:(1)保留最长的腿,然后将短腿中代价之最小的一部分删除,直至长腿占比例>1/2;
(2)删除最长腿,代价+递归调用;
然后最终的结果是(1)(2)两种情况的最小值;

发表于 2016-07-27 17:38:45 回复(0)
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<climits>
using namespace std;

bool compare(pair<int,int> a,pair<int,int> b){
    return a.second<b.second;
}


int main(){
	int n;
    vector<int> res;
    while(cin>>n){
        map<int,int> m;
        vector<pair<int,int> > con;
        vector<int> length(n);
        for(int i=0;i<n;i++){
            cin>>length[i];
		}
        for(int i=0;i<n;i++){
            int tmp;
            cin>>tmp;
            con.push_back(make_pair(length[i],tmp));
            if(m.find(length[i])!=m.end()){
                m[length[i]]++;
			}else{
                m[length[i]]=1;
			}
		}
        sort(con.begin(),con.end(),compare);
        
        int minValue = INT_MAX;
        int last = 0;
        for(map<int,int>::iterator it = m.begin();it!=m.end();it++){
            int tmp = it->second;
            int count = tmp-1;
			if(count<last){
                count = last-count;
			}else{
                count=0;
			}
            int value = 0;
            for(int i=0;i<n;i++){
                if(con[i].first>it->first){
                    value +=con[i].second;
				}
                if(con[i].first<it->first&&count){
                    value+=con[i].second;
                    count--;
				}
				
			}
			last+=it->second;
            minValue = min(minValue,value);
		}
        cout<<minValue<<endl;
	}
    return 0;
}
编辑于 2016-07-22 23:26:11 回复(0)
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
 
#include <limits.h>
 
intmain()
{
    intn;
    cin >> n;
    vector<int> l(n);
    vector<int> d(n);
    intflag[106] = {0};
    for(inti=0; i<n; i++)
        cin >> l[i];
    for(inti=0; i<n; i++)
        cin >> d[i];
    intcost = INT_MAX;
    for(inti=0; i<n; i++)
    {
        if(flag[l[i]])
            continue;
        intmaxl = l[i];
        flag[106] = 1;
        vector<int> value;
        inteq_nr = 0;
        inttmp = 0;
        for(intj=0; j<n; j++)
        {
            if(l[j] == maxl)
                eq_nr ++;
            elseif(l[j] < maxl)
                value.push_back(d[j]);
            elseif(l[j] > maxl)
                tmp += d[j];
        }
        if(eq_nr > value.size())
            cost = cost > tmp ? tmp : cost;
        else
        {
            sort(value.begin(), value.end());
            for(intk=0; k<value.size()-eq_nr+1; k++)
                tmp += value[k];
            cost = cost > tmp ? tmp : cost;
        }
    }
    cout << cost << endl;
    return0;
}

发表于 2016-07-18 10:39:47 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
  
intmain()
{
    intn;
    while(cin>>n)
    {
        vector<int>l,d,d_cut;
        inta[106]={0};
        intli,di;
        for(inti=0;i<n;i++)
        {
            cin>>li;
            l.push_back(li);
            a[li]++;
        }
        intminCost=0;
        for(inti=0;i<n;i++)
        {
            cin>>di;
            d.push_back(di);
            minCost+=di;
        }
        for(inti=105;i>0;i--)
        {
            intcost=0;
            d_cut.clear();
            if(a[i])
            {
                intcutLegNum=l.size()-a[i];
                for(intj=i+1;j<=105;j++)
                {
                    cutLegNum-=a[j];
                }
                cutLegNum-=(a[i]-1);
                for(intk=0;k<n;k++)
                {
                    if(l[k]<i)
                        d_cut.push_back(d[k]);
                    if(l[k]>i)
                        cost+=d[k];
                }
                if(cutLegNum>0)
                {
                    sort(d_cut.begin(),d_cut.end());
            for(intk = 0; k <cutLegNum; k++)
                        cost+=d_cut[k];
                    if(cost<minCost)
                        minCost=cost;
                }    
            }
        }
        cout<<minCost<<endl;
    }
    return0;
}

发表于 2016-06-27 14:48:19 回复(0)
1.统计每个整数出现的次数count[]
2.计算预计去掉个数:x=n-2*count(i)
3.判断是否可以作为候选最大值:计算比num[i]大的count之和sum,若sum<=x,则此数可作为候选最大值
4.比num[i]大的所有代价和,加上比num[i]小的代价最小和,作为最小值候选
5.循环所有候选最大值,然后更新最小的代价值。
6.输出最小代价值
发表于 2016-04-17 17:21:04 回复(0)

 #include <iostream>

using namespace std;

// 升序排列arr, temparr做同样的位置改变
void quick_sort(int arr[], int low, int high, int temparr[]) {
	if (low < high) {
		int key = arr[low];
		int key_t = temparr[low];
		int i = low, j = high;
		while (i < j) {
			while (i < j && arr[j] >= key)	--j;
			arr[i] = arr[j];
			temparr[i] = temparr[j];
			while (i < j && arr[i] <= key)	++i;
			arr[j] = arr[i];
			temparr[j] = temparr[i];
		}

		arr[i] = key;
		temparr[i] = key_t;
		quick_sort(arr, low, i - 1, temparr);
		quick_sort(arr, i + 1, high, temparr);
	}
}

// 在已排好序的arr中,按照3temparr中的值进行二级排序
void resort(int arr[], int len, int temparr[], int legIndex[]) {
	int t = arr[0];
	int low = 0, high = 0;
	legIndex[0] = 0;
	for (int i = 1;i < len;++i) {
		if (t == arr[i]) {
			++high;
			legIndex[i] = low;
		}
		else {
			if (low != high) {
				quick_sort(temparr, low, high, arr);
			}
			t = arr[i];
			low = high = i;
			legIndex[i] = low;
		}

		if(i == len - 1 && low != high)
			quick_sort(temparr, low, high, arr);
	}
}

void getResult(int lLen[], int lVal[], int lIndex[], int n, int &rslt) {
	int t = lLen[0], cnt = 0;
	int rslt_t = 0;
	for (int i = 0;i < n;++i) {
		if (t == lLen[i]) {
			++cnt;
		}
		else {
			for (int j = i;j < n;++j)
				rslt_t += lVal[j];			//砍掉大于目标腿长的
			if ((0 != lIndex[i - 1]) && (cnt <= i / 2)) {
				int *arr = new int[lIndex[i - 1]];
				for (int j = 0;j < lIndex[i - 1];++j)
					arr[j] = lVal[j];
				quick_sort(arr, 0, lIndex[i - 1] - 1, arr);

				for (int k = 0;k < lIndex[i - 1] - cnt + 1;++k)
					rslt_t += arr[k];

				delete[] arr;
			}

			if (0 == lIndex[i - 1])
				rslt = rslt_t;
			if (rslt_t < rslt)
				rslt = rslt_t;
			rslt_t = 0;
			t = lLen[i];
			cnt = 1;
		}

		if (i == n - 1) {
			if ((0 != lIndex[i - 1]) && (cnt <= i / 2)) {
				int *arr = new int[lIndex[i - 1]];
				for (int j = 0;j < lIndex[i - 1];++j)
					arr[j] = lVal[j];
				quick_sort(arr, 0, lIndex[i - 1] - 1, arr);

				for (int k = 0;k < lIndex[i - 1] - cnt + 1;++k)
					rslt_t += arr[k];

				delete[] arr;
			}

			if (0 == lIndex[i - 1])
				rslt = rslt_t;
			if (rslt_t < rslt)
				rslt = rslt_t;
		}
	}
}

int main()
{
	int n = 0;
	int *legLen = NULL;
	int *legVal = NULL;
	int *legIndex = NULL;	//每种桌腿的首个位置
	int sum_val_min = 0;

	while (cin >> n) {
		legLen = new int[n];
		legVal = new int[n];
		legIndex = new int[n];

		for (int i = 0;i < n;++i)
			cin >> legLen[i];
		for (int i = 0;i < n;++i)
			cin >> legVal[i];

		quick_sort(legLen, 0, n - 1, legVal);
		resort(legLen, n, legVal, legIndex);

		getResult(legLen, legVal, legIndex, n, sum_val_min);

		cout << sum_val_min << endl;

		/*for (int i = 0;i < n;++i)
			cout << legLen[i] << "  ";
		cout << endl;
		for (int i = 0;i < n;++i)
			cout << legVal[i] << "  ";
		cout << endl;
		for (int i = 0;i < n;++i)
			cout << legIndex[i] << "  ";
		cout << endl;*/

		delete[] legLen;
		delete[] legVal;
		delete[] legIndex;
	}

	return 0;
}
代码有点长,有两个排序辅助函数,两次排序主要是对腿长数组和代价数组进行排序,按照腿长升
序,相同腿长按照代价再次进行升序排列。
排序之后就好计算了,依次计算保留某长度的腿需要消耗的最小代价,首先比目标长度大的毫无疑问
全部砍掉,然后判断是否需要砍掉部分小于该长度的腿,保证目标腿长的数量超过一半。对小于目标
腿长的进行再次排序,确定需要砍掉的数量后,直接从开始砍就行。
写得非常复杂。。。将就看吧

编辑于 2016-04-11 22:23:22 回复(0)