好装箱问题606bin.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

class Node
{
	friend class List;
	friend class Iterator;
	private:
		int data;
		Node *next;
};

class List                           //建立一个链表
{
   friend class Iterator;
   public:
	   List(){first=0;}
	   ~List();
	   List &Insert(int k,int &x);
	   List &Delete(int k,int &x);
	   List &Compare(int t);
   private:
	   Node *first;
};

List::~List()
{
	Node *next;
	while(first)
	{
		next=first->next;
		delete first;
		first=next;
	}
}

List &List::Insert(int k,int &x)
{
	if(k<0) return *this;
	Node *p=first;
	int fig=1;
	for(int i=fig;i<k&&p;i++)
		p=p->next;
	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 k,int &x)
{
	if(k<0) return *this;
	Node *p=first;
	if(k==1)
		first=first->next;
	else
	{
		Node *q=first;
		for(int index=1;index<k-1&&q;index++)
			q=q->next;
		if(!q&&!q->next) return *this;
		p=q->next;
		q->next=p->next;
	}
	x=p->data;
	delete p;
	return *this;
}
List &List::Compare(int t)
{
	Node *q=first;
	Node *p=new Node;
	p->data=t;
	Node *r=q;
	while(q->data<t)
	{
		r=q;
		q=q->next;
	}
	if(q->data==t)
		return *this;
	else
		if(q==r)
		{
			p->next=first;
			first=p;
		}
		else
		{
			r->next=p;
			p->next=q;
		}
	return *this;
}
class Iterator
{
  public:
	  int* Init(List &c)
	  {
		  loca=c.first;
		  if(loca)
			  return &loca->data;
		  return 0;
	  }
	  int* Next()
	  {
		  if(!loca) return 0;
		  loca=loca->next;
		  if(loca)
			  return &loca->data;
		  return 0;
	  }
  private:
	  Node *loca;
};

int main()
{
	int n,c,t,x,count=1;
	in>>n>>c;
	List *L=new List[c+1],P;
	L[c].Insert(0,count);
	P.Insert(0,c);
	Iterator I,In;
	for(int i=1;i<=n;i++)
	{
		in>>t;
		int *s=In.Init(P);
		while(*s<t)
			s=In.Next();
		while(true)
		{
			int *q=I.Init(L[*s]);
			if(q)
			{
				if(*s==c)
				{
					count++;
				    out<<i<<' '<<*q<<endl;
				    L[*s].Delete(1,x);
				    L[*s-t].Insert(0,x);
				    P.Compare(*s-t);
					L[c].Insert(0,count);
				    break;
				}
				else
				{
				    out<<i<<' '<<*q<<endl;
				    L[*s].Delete(1,x);
				    L[*s-t].Insert(0,x);
				    P.Compare(*s-t);
					break;
				}
			}
			else
				s=In.Next();
		}
	}
	out<<count-1;
	delete[]L;
	return 0;
}