[C++知识库]大模拟 CSP DHCP服务器

题目链接：https://www.acwing.com/problem/content/description/3416/

题目分析：

这道题目实际难度不大，给人的感觉更像是在做阅读理解。主要难点在于提炼出有用的信息。其实题目中试题背景部分并不重要，我们直接看问题描述后面的内容即可。在实现细节部分，题目要求我们初始化ip地址池等操作，可以看出，我们主要做的就是维护一个ip地址池。而维护的方式也在该部分给的十分详细，只需按照给定的需求来编写代码，也就不会出现问题。主要容易漏掉的地方就是地址过期后状态的改变了。
所以总的来说题目要求的就是：

• 维护一个ip地址池。每个ip的相关信息有：状态、过期时间、占用者。
• 根据题目的要求对客户端发来的报文进行处理。
• 及时对ip状态进行更新。

可以用表格整理得ip的一些相关信息：

根据这些信息，按照题目描述的报文处理方法进行代码的编写即可。

数据结构分析：

利用结构体IP记录ip相关信息：

struct IP
{
	int ip;//ip号，不是必要的，可直接用数组中的下标表示其ip号
	Type state;//状态
	int time;//过期时间 
	string owner;//占有者
	IP():ip(0),state(Unassigned),time(0),owner(""){}
}IPs[MAX_N];

其中Type的定义如下：

//未分配、待分配、占用、过期
enum Type {Unassigned,To_be_allocated,Occupied,Overdue};

100分代码：

#include<iostream>
#include<string>
#include<vector>
#define endl '\n'
using namespace std;
const int MAX_N=1e4+10;
string host;
enum Type {Unassigned,To_be_allocated,Occupied,Overdue};
struct IP
{
	int ip;
	Type state;
	int time;//过期时间 
	string owner;
	IP():ip(0),state(Unassigned),time(0),owner(""){}
}IPs[MAX_N];
int N,Tdef,Tmax,Tmin;
void update(int now)//按过期时间对ip状态进行更新 
{
	for(int i=1;i<=N;i++)
	{
		if(IPs[i].time!=0&&IPs[i].time<=now)
		{
			if(IPs[i].state==Occupied)
			{
				IPs[i].state=Overdue;
				IPs[i].time=0;
			}
			else
			{
				IPs[i].state=Unassigned;
				IPs[i].time=0;
				IPs[i].owner="";
			}
		}
	}
}
void undo(string name)//将客户机name的所有待分配ip改为未分配状态 
{
	for(int i=1;i<=N;i++)
	{
		if(IPs[i].state==To_be_allocated&&IPs[i].owner==name)
		{
			IPs[i].state=Unassigned;
			IPs[i].owner="";
			IPs[i].time=0;
		}
	}
}
void set_time(int ip,int time,int now)//设置对应ip的过期时间,time为客户端的期望过期时间 
{
	if(!time)IPs[ip].time=now+Tdef;
	else 
	{
		time=min(time,now+Tmax);
		time=max(time,now+Tmin);
		IPs[ip].time=time;
	}
}
int main()
{
	cin>>N>>Tdef>>Tmax>>Tmin>>host;
	for(int i=1;i<=N;i++)IPs[i].ip=i;
	int n;
	cin>>n;
	int now,ip,time;
	string from,to,cat;
	while(n--)
	{
		cin>>now>>from>>to>>cat>>ip>>time;
		
		//以下情况不予处理,这里就是完全按照题目要求写的 
		if(to!=host&&to!="*"&&cat!="REQ")continue;
		else if(cat!="REQ"&&cat!="DIS")continue;
		else if((to=="*"&&cat!="DIS")||(to==host&&cat=="DIS"))continue;
		
		update(now);//important
		if(cat=="DIS")
		{
			int ip_last=0,ip_unassigned=0,ip_overdue=0;
			for(int i=1;i<=N;i++)
			{
				//只记录第一个（最小的） 
				if(IPs[i].state==Unassigned&&ip_unassigned==0)ip_unassigned=IPs[i].ip; 
				if(IPs[i].state==Overdue&&ip_overdue==0)ip_overdue=IPs[i].ip;
				
				if(IPs[i].owner==from)
				{
					ip_last=IPs[i].ip;//上一次分配给该客户机的ip 
					break;
				}
			}
			if(ip_last==0&&ip_unassigned==0&&ip_overdue==0)continue;
			//确定要分配的ip 
			int choice=0;
			if(ip_overdue)choice=ip_overdue;
			if(ip_unassigned)choice=ip_unassigned;
			if(ip_last)choice=ip_last;
			//改变对应ip的分配状态及相关信息 
			IPs[choice].state=To_be_allocated;
			IPs[choice].owner=from;
			set_time(choice,time,now);
			cout<<host<<" "<<from<<" OFR "<<choice<<" "<<IPs[choice].time<<endl;
		}else if(cat=="REQ")
		{
			if(to!=host)
				undo(from);
			else
			{
				if(ip<=N&&IPs[ip].owner==from)
				{
					IPs[ip].state=Occupied;
					set_time(ip,time,now);
					cout<<host<<" "<<from<<" ACK "<<ip<<" "<<IPs[ip].time<<endl;
				}
				else
					cout<<host<<" "<<from<<" NAK "<<ip<<" 0"<<endl;
			}
		}
	}
	return 0;
}

还是没懂的话，我还找到了一个视频讲解：点我