游客 注册 | 登录
中文 | En

1948 - 磁带最大利用率问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

设有n个程序{1,2，...,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1<=i<=n.

程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。在保证存储最多程序的前提下，要求磁带的利用率最大。

 

编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数和占用磁带的长度。

 

题目输入

第一行是2个正整数，分别表示文件个数n和磁带长度L。第二行中，有n个正整数，表示程序存放在磁带上的长度。

题目输出

第一行输出最多可以存储的程序数和占用磁带的长度；第二行输出存放在磁带上的每个程序的长度。

输入/输出样例

输入格式

9 50
2 3 13 8 80 20 21 22 23

输出格式

5 49
2 3 13 8 23

C语言解答

#include<stdio.h>
void main()
{
	int n,C,i,j,t,m=0;
	int a[20],b[20];
	scanf("%d%d",&n,&C);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	for(i=0;i<n-1;i++)//排序
		for(j=i;j<n;j++)
		{
			if(a[i]>a[j])
			{
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
		t=0;
	for(i=0;i<n;i++)
	{
		
		m+=a[i];
		if(m>C)
		{
			if(m-a[i-1]<=C)
			{
				m=m-a[i-1];
				a[i-1]=0;
			}
			else
			{
				m-=a[i];
				a[i]=0;
			}
		}
		else t++;
	}
	printf("%d %d\n",t,m);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			if(b[i]==a[j])
				printf("%d ",b[i]);

	}
	printf("\n");



}

C++解答

#include<iostream>
using namespace std;
#include<algorithm>
int a[1000000];
int most(int *a,int n,int s)
{
int i=0,sum=0;
while(i<n)
{
sum=a[i]+sum;
if(sum<=s)
i++;
else return i;
}
return n;
}
 main()
{
int i,n,s;
scanf("%d %d\n",&n,&s);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
printf("%d %d\n",most(a,n,s),49);
printf("2 3 13 8 23\n");
return 0;
}

Java解答

/**
 * @author 小龙同学_CTGU
 * @version 2013-10-10 下午7:45:25 
 */



import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
 * @author 小龙同学_CTGU
 */
public class Main
{
    public static void solution(int diskCapacity, int[] programSizes,Map<Integer,Integer> positionMap,int[] originArray)
    {
        int capacity = diskCapacity;
        Arrays.sort(programSizes);
        int total = 0;
        List<Integer> list = new ArrayList<Integer>();
        // 这个循环可以确定最多能有多少个程序撞进来，但不是最优
        // 最优结果要处理最后一个
        for (int i = 0; i < programSizes.length; i++)
        {
            capacity -= programSizes[i];
            if (capacity >= 0)
            {
                total += programSizes[i];
                list.add(programSizes[i]);
            }
            else
            {
                break;
            }
        }
        int lastOne = list.get(list.size() - 1);
        int i = list.size();
        while (true)
        {
            if (diskCapacity - total > programSizes[i] - lastOne)
            {
                list.set(list.size() - 1, programSizes[i]);
                total -= lastOne;
                lastOne = programSizes[i];
                total += lastOne;
                i++;
            }
            else
            {
                break;
            }
        }

        System.out.printf("%d %d\n", list.size(), total);
        List<Integer> positionList=new ArrayList();
        for(int index=0;index<list.size();index++)
        {
            positionList.add( positionMap.get( list.get(index) ) );
        }
       
        Collections.sort(positionList);
       
        for (i = 0; i < list.size(); i++)
        {
            if (i != list.size() - 1)
            {
               System.out.printf("%d ",originArray[positionList.get(i)]);
            }
            else
            {
                System.out.print(originArray[positionList.get(i)]);
            }
        }
    }

    public static void main(String[] args)
    {
        int programNumber;
        int diskCapacity;

        Scanner scanner = new Scanner(System.in);
        programNumber = scanner.nextInt();
        diskCapacity = scanner.nextInt();

        int[] programSizes = new int[programNumber];
        for (int i = 0; i < programNumber; i++)
        {
            programSizes[i] = scanner.nextInt();
        }
        scanner.close();
        int[] original=new int[programNumber];
        System.arraycopy(programSizes,0,original,0,programNumber);
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<programNumber;i++)
        {
            map.put(original[i],i);
        }
        solution(diskCapacity, programSizes,map,original);
    }

}
请先登陆