2 条题解

  • 0
    @ 2025-3-21 18:08:28
    #include<iostream>
    #include<vector>
    #include<string>
    #include<algorithm>
    #include<unordered_set>
    #include<set>
    #include<unordered_map>
    #include<queue>
    using namespace std;
    bool islastrount(const set<int>& uset, const unordered_set<int>& toerase)//是否是最后一轮删除
    {
    	for (const auto& e : uset)
    	{
    		if (toerase.count(e) == 0)
    		{
    			return false;
    		}
    	}
    	return true;
    }
    int main()
    {
    	int N, E, T, P;//N:发动机总数,E:手动启动数(E行),T:手动启动时刻,P:启动发动机的编号
    	cin >> N >> E;
    	set<int> uset;
    	for (int i = 0; i < N; i++)
    	{
    		uset.insert(i);//在集合中插入所有发动机编号
    	}
    	unordered_map<int, unordered_set<int>> setup;//<启动时间,该启动时间的发动机编号>
    	for (int i = 0; i < E; i++)
    	{
    		cin >> T >> P;
    		if (setup.find(T) == setup.end())//若该时间点不存在,则创建该时间点的启动编号集合
    		{
    			setup.insert({ T,unordered_set<int>{P} });
    		}
    		else//若该时间点存在,则在集合插入编号
    		{
    			setup[T].insert(P);
    		}
    	}
    
    	queue<int> toerase;
    	int i;
    	for (i = 0; !islastrount(uset,setup[i]); i++)
    	{
    		for (const auto& e : setup[i])
    		{
    			toerase.push(e);//将i时间点要启动的发动机编号加入队列
    		}
    		while (!toerase.empty())//当队列非空
    		{
    			if (uset.count(toerase.front()) == 1)//如果要删除的队头在未发动的集合中
    			{
    				uset.erase(toerase.front());//发动该机器
    				
    				setup[i + 1].insert({ 
    					(toerase.front() + N - 1) % N ,
    					(toerase.front() + 1) % N 
    					});	//并将相邻机器加入i+1时刻的待发动集合中
    				toerase.pop();//队头删除
    			}
    			else//若该机器已经发动,则直接删除
    			{
    				toerase.pop();
    			}
    		}
    	}
    	cout << uset.size()<<endl;
    	for (const auto& e : uset)
    	{
    		cout << e << ' ';
    	}
    	
    }
    
    
    
    • 0
      @ 2025-3-6 16:22:59

      看似简单,其实坑很多,花了很多时间。

      
      #include <iostream>
      #include <vector>
      using namespace std;
      
      vector<vector<int>> height(1002);
      vector<int> hand(1002);     //初始化-1,索引为时间,数值为id
      
      int N;
      int E;
      int mytime = 0;
      int num = 0;                        //输出
      vector<int> ids;                    //输出
      
      int test(vector<int> light, int N)
      {
      	int flag = 1;
      	for (int i = 0; i < N; i++)
      	{
      		if (light[i] == 0)
      		{
      			flag = 0;
      			break;
      		}
      	}
      	return flag;
      }
      
      
      void Plan()
      {
      	vector<int> light(N);
      	vector<int> light2(N);
      	fill(light.begin(), light.end(), 0);
      	fill(light2.begin(), light2.end(), 0);
      	int flag = 0;
      	for (mytime = 0; mytime <= N; mytime++)
      	{
      		//检索
      		if (test(light, N) == 1)
      		{
      			break;
      		}
      		else {
      			num = 0;            //清空
      			ids.clear();
      		}
      		for (int i = 0; i < N; i++)       //扩散
      		{
      			if (light[i] == 1)
      			{
      				if (i == 0)
      				{
      					if (light[1] == 0 && light2[1] == 0)
      					{
      						light2[1] = 1;
      						num++;
      						ids.push_back(1);
      					}
      					if (light[N - 1] == 0 && light2[N - 1] == 0)
      					{
      						light2[N - 1] = 1;
      						num++;
      						ids.push_back(N - 1);
      					}
      				}
      				else if (i < N - 1)
      				{
      					if (light[i - 1] == 0 && light2[i - 1] == 0)
      					{
      						light2[i - 1] = 1;
      						num++;
      						ids.push_back(i - 1);
      					}
      					if (light[i + 1] == 0 && light2[i + 1] == 0)
      					{
      						light2[i + 1] = 1;
      						num++;
      						ids.push_back(i + 1);
      					}
      				}
      				else
      				{
      					if (light[0] == 0 && light2[0] == 0)
      					{
      						light2[0] = 1;
      						num++;
      						ids.push_back(0);
      					}
      					if (light[N - 2] == 0 && light2[N - 2] == 0)
      					{
      						light2[N - 2] = 1;
      						num++;
      						ids.push_back(N - 2);
      					}
      				}
      			}
      		}
      		//light同步
      		for (int i = 0; i < N; i++)
      		{
      			if (light2[i] == 1) light[i] = 1;
      		}
      		//手动
      		if (height[mytime].size() != 0)
      		{
      			int tmpNum = height[mytime].size();
      			for (int i = 0; i < tmpNum; i++)
      			{
      				int tempInt = height[mytime][i];
      				if (light[tempInt] == 0)
      				{
      					light[tempInt] = 1;
      					num++;
      					ids.push_back(tempInt);
      				}
      			}
      		}
      	}
      }
      
      int main() {
      	cin >> N;
      	cin >> E;
      	vector<int> temp;
      	int tempInt;
      	int tempInt2;
      	fill(hand.begin(), hand.end(), -1);
      	for (int i = 0; i < E; i++)
      	{
      		cin >> tempInt;
      		cin >> tempInt2;
      		hand[tempInt] = tempInt2;
      		height[tempInt].push_back(tempInt2);    //新结构体
      	}
      	Plan();
      	cout << num << endl;
      	for (int i = 0; i < num; i++)
      	{
      		cout << ids[i] << " ";
      	}
      	return 0;
      }
      /*
      输入
      
      8 2 0 2 0 6
      
      输出
      
      2 0 4
      */
      
      
      
      • 1

      信息

      ID
      105
      时间
      1000ms
      内存
      256MiB
      难度
      7
      标签
      (无)
      递交数
      471
      已通过
      101
      上传者