1199D - Welfare State（思维）

我就是我 2021-07-16 15:04 444阅读 0赞

[题目][Link 1]

题意：对于n个公民，我们知道其一开始的各自的金钱。现在我们有两种操作：1.直接将各个钱数小于k的公民的钱数转变为k。2.将第p个人的钱数抓变为k。问经过q次操作后，每个人最后的钱数为多少？

思路：我们将一个人的金钱变化阶段定为两个，在q次操作中一个人在最后一次操作2，金钱直接变为了m0,后面还可能会有一些操作1，我们只需将m0变为max(m0,在后面的操作1中最大的k)，这就是此人最后的金钱数。在此思路也就明了了，我们只需记录每一次操作的从当前操作到最后一次的操作中所有操作2中的最大的k。还有我们每个人最后一次操作1的次序，如果没有则令其为0.细节见代码。

Code

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e5 + 5;
    int lst[Max];
    int ma[Max];
    int ls[Max];
    int man[Max][2];
    
    int main()
    { 
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cin >> lst[i];
    	}
    	int m;cin >> m;
    	for (int i = 1;i <= n;i++)
    	{ 
    		man[i][0] = 0;man[i][1] = lst[i];
    	}
    	for (int i = 1;i <= m;i++)
    	{ 
    		int a, b, c;cin >> a;if (a == 1)
    		{ 
    			cin >> b >> c;
    			man[b][0] = i;man[b][1] = c;
    		}
    		if (a == 2)
    		{ 
    			cin >> b;ls[i] = b;
    		}
    	}
    	for (int i = m;i >= 1;i--)
    	{ 
    		ma[i] = max(ma[i + 1], ls[i]);
    	}
    	ma[0] = ma[1];
    	for (int i = 1;i <= n;i++)
    	{ 
    		int ans;
    
    		cout << max(man[i][1], ma[man[i][0]]) << " ";
    	}
    }

[Link 1]: https://codeforces.ml/problemset/problem/1199/D