030300506bin.cpp

装箱问题：在装箱问题中

#include<iostream>
#include<fstream>
using namespace std;
#include"time.h"
clock_t start,finish;
#define M 10000
class BadInput{};
class list;

class node{
	
	friend class list;
    public:
		int data;
		node *next;
};

class list{
	//private:
		friend class Iterator;
			
    	public:
            node *first;
			list(){first=0;}
			~list();
			bool empty() const {return first==0;}
			int length() const;
			bool retrieve(int k,int x) const;
			int locate(const int x) const;
			list&insert(int k,int x);
			list&Delete(int &x);
			void Output(ostream &cout)const;
};
list::~list()
{
	node *next;
	while(first){
		next=first->next;
		delete first;
		first=next;
	}
}
int list::length() const
{
	node *current=first;
	int len=0;
	while(current){
		len++;
		current=current->next;
	}
	return len;
}
bool list::retrieve(int k,int x) const
{
	if (k<1)return false;
	node *current=first;
	int index=1;
	while(index<k&&current){
		current=current->next;
		index++;
	}
	if (current){
		x=current->data;
		return true;
	}
	return false;
}
int list::locate(const int x) const
{
	node *current=first;
	int index=1;
	while(current&&current->data!=x){
		current=current->next;
		index++;
	}
	if (current) return index;
	return 0;
}
list&list::insert(int k,const int x)
{
	if(k<0)cout<<"outofbound"<<endl;
	node *p=first;
	for(int index=1;index<k&&p;index++)
		p=p->next;
	if(k>0&&!p)cout<<"outofbound"<<endl;
	node *y=new node;
	y->data=x;
	if (k){
		y->next=p->next;
		p->next=y;
	}
	else{
		y->next=first;
		first=y;
	}
	return *this;
}
list&list::Delete(int&x)
{
	node *current=first,
		 *trail=0;
	while(current&&current->data!=x)
	{
		trail=current;
		current=current->next;
	}
	if(!current)throw BadInput();
	x=current->data;
	if(trail)trail->next=current->next;
	else first=current->next;
	delete current;
	return *this;
}
void list::Output(ostream &cout)const
{
	node *current;
	for(current=first;current;current=current->next)
		cout<<current->data<<" ";
}

int n,c,mod,box=1,tem,renew,duo;
main()
{
    start=clock();
    ifstream in ("input.txt");
	if (!in){
		cout<<"can't open input file\n";
		return 1;
	}
	ofstream out ("output.txt");
	if (!out){
		cout<<"can't open output file\n";
		return 2;
	}
	
	in>>n>>c;
	int *orig=new int[n+1];
	int *avail=new int[n+1];
	for(int i=1;i<=n;i++)
		in>>orig[i];
	for(i=1;i<=n;i++)
		avail[i]=0;
	list *ht=new list[c+1];
    for(i=1;i<=n;i++)
	{
		if(i==1)
		{
			duo=c-orig[i];
			ht[duo].insert(0,i);//将第一个数的余数插入
           // ht[duo].Output(cout);
			avail[i]=box;
		//	cout<<endl;
		}
		
		else 
		{
			for(int j=orig[i];j<=c;j++)
			{  
				//cout<<"j"<<j<<endl;
			    if(ht[j].first)
				{ 
				    tem=ht[j].first->data;
				    avail[i]=avail[tem];
				    ht[j].Delete(tem);//将已经访问的接点删去
                    renew=j-orig[i];
				    if(renew)
					    ht[renew].insert(0,tem);//还有剩余空间则再插入所剩空间大小对应的链表					
				    break;
				} 
			    if(j==c)//不存在，则继续开辟新的箱子
				{ 
				   avail[i]=++box;
				   duo=c-orig[i];
				   ht[duo].insert(0,i);
				} 
			} 
		}
	}
	for(i=1;i<=n;i++)
	{
        out<<i<<" "<<avail[i];
		out<<endl;
	}
	out<<box;		
    finish=clock();
	cout<<finish-start<<endl;
	return 0;
}