Codeforces Round 935 (Div. 3) （A~G）

1945A - Setting up Camp 

        题意：三种人安排住宿,a只能跟自己住,b只能三个人住,c能1~3个人，问最终最少房间数

        思路：a单独安排,b放一起,不足三个人的用c补,然后c按照3人一房间尽可能分配

        

void solve() 
{
	int a , b , c;
	cin >> a >> b >> c;
	int ans = a + b / 3;
	b %= 3;
	int res = b + c;
	if(res == 0){
		cout << ans << endl;
		return;
	}
	if(b){
		if(res < 3){
			cout << -1 << endl;
		}
		else{
			cout << ans + (res - 1) / 3 + 1 << endl;
		}
	}
	else{
		cout << ans + (res - 1) / 3 + 1 << endl;
	}
}      

1945B - Fireworks 

        题意：装置A每a分钟放一次烟花,装置B每b分钟放一次烟花,烟花能存在m分钟,求空中同时存在最多多少烟花.

        思路：两只烟花必然能同时放,然后再看接下来m分钟能放多少只烟花,这样必然最优

void solve() 
{
	LL a , b , m;
	cin >> a >> b >> m;
	//同一时间发射
	LL en = m;
	cout << (en / a) + (en / b) + 2<< endl;
}  

1945C - Left and Right Houses 

        题意：给定01串,要求从中间某个位置分开,其中左侧0的数量大于等于1的数量,右侧1的数量大于等于0的数量,求满足条件的最靠近中心的位置。

        思路：直接模拟

void solve() 
{
	double n;
	cin >> n;
	string s;
	cin >> s;
	s = " " + s;
	int left = 0, right = 0;
	for(int i = 1 ; i <= (int)n ; i ++){
		right += (s[i] == '1');
	}	
	vector<double>ans;
	int left_cnt = 0 , right_cnt = n;
	for(int i = 0 ; i <= n ; i ++){
		if(i > 0){
			if(s[i] == '0'){
				left++;
			}
			if(s[i] == '1'){
				right--;
			}
			left_cnt++;
			right_cnt--;
		}
		//在i的右边
		if((left_cnt + 1) / 2 <= left && (right_cnt + 1) / 2 <= right){
			ans.pb(i);
		}
		
	}
	int out = 0;
	int maxx = 1e8;
	for(int i = 0 ; i < ans.size() ; i ++){
		double diff = abs(n / 2 - ans[i]);
		if(diff < maxx){
			out = ans[i];
			maxx = diff;
		}
	}
	cout << out << endl;
}  

 1945D - Seraphim the Owl 

        题意：

        思路：最终位置必须为a数组,一旦最终位置确定了,那么其中间的选a数组还是b数组都行，因此除了最终位置需要花费a数组的硬币,其余都是a或b的最小值。

void solve() 
{
	cin >> n >> m;
	LL a[n + 5] , b[n + 5];
	for(int i = 1 ; i <= n ; i ++)
		cin >> a[i];
	for(int i = 1 ; i <= n ; i ++)
		cin >> b[i];
	//如果b[i] < a[i] , 那么就等着前面 , 否则就选上
	LL ans = llinf;
	LL pre = 0;
	for(int i = m + 1 ; i <= n ; i ++){
		pre += min(a[i] , b[i]);
	}	
	for(int i = m ; i >= 1 ; i --){
		ans = min(ans , a[i] + pre);
		pre += min(a[i] , b[i]);
	}
	cout << ans << endl;
}      

 1945E - Binary Search 

        题意：

        思路：可以想到,对于一个给定的排列,其算法中所有需要跟x进行比较的数的位置都是能确定的，如果x所在位置不在需要比较的位置里面,那么只需要将x放到最终的l上面就能满足题意了，因此我们可以枚举第一步,将x放在不需要比较的位置上，然后再将x放入最终的l即可。

void solve() 
{
	int n , x;
	cin >> n >> x;
	int pos = 0;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		if(a[i] == x)
			pos = i;
	}
	for(int i = 1 ; i <= n ; i ++){
		swap(a[i] , a[pos]);
		int l = 1 , r = n + 1;
		vector<int>path;
		while(r - l > 1){
			int mid = (l + r) / 2;
			if(a[mid] <= x){
				l = mid;
			}
			else
				r = mid;
			path.pb(mid);
		}
		int f = 1;
		for(auto it : path){
			if(it == i){
				f = 0;
				break;
			}
		}
		if(f){
			cout << 2 << endl;
			cout << i << " " << pos << endl;
			cout << i << " " << l << endl;
			return;
		}
		swap(a[i] , a[pos]);
	}
}   

1945F - Kirill and Mushrooms 

        题意：现有n个蘑菇,每个蘑菇有一个对应的魔力值,还给定了一个排列,现在需要用蘑菇来制作药水,规定药水的魔力值为所用蘑菇中最小的魔力值 * 所用蘑菇数。同时若用了k个蘑菇,那么排列的前k - 1个数所对应的蘑菇魔力值将变为0.同时魔力值为0的蘑菇不能被用作制作药水。

        思路：枚举拿蘑菇的数量。贪心的思想,每次都拿当前魔力值最高的蘑菇,同时因为多了一个蘑菇,因此会有一个蘑菇的魔力值变成0，若这个0魔力值的蘑菇在所选中蘑菇里面，就重新再拿一个蘑菇，如此不断往复。

void solve() 
{
	cin >> n;
	pair<int,int>a[n + 5];
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i].x;
		a[i].y = i;
	}
	int p[n + 5];
	p[0] = 0;
	for(int i = 1 ; i <= n ; i ++)
		cin >> p[i];
	auto cmp = [&](pair<int ,int> a , pair<int,int> b){
		return a.x > b.x;
	};
	a[n + 1].x = 0;
	sort(a + 1 , a + n + 1 , cmp);
/*	for(int i = 1 ; i <= n ; i ++){
		cout << a[i].x <<" " << a[i].y << endl;
	}*/
	map<int,int>mp;//是否在篮子里
	map<int,int>vis;//这么多不能在篮子里
	LL ans = -1;
	LL out = 0;
	int id = 0;
	int minn = llinf;
	for(int cnt = 1 ; id <= n && cnt <= n ; cnt ++ , id++){
		if(id > n)
			break;
		//ban
		vis[p[cnt - 1]] = 1;
		//out
		if(mp.count(p[cnt - 1])){//有了
			while(id <= n && vis.count(a[id].y)){
				id++;
			}
			minn = a[id].x;
			mp[a[id].y] = 1;
			id++;
		}
		//pick
		while(id <= n && vis.count(a[id].y)){
			id++;
		}
		minn = a[id].x;
		mp[a[id].y] = 1;
		if(minn * cnt > ans){
			ans = minn * cnt;
			out = cnt;
		}
	}
	cout << ans << " " << out <<endl;
}  

1945G - Cook and Porridge 

        题意：

        思路：看代码

// Problem: G. Cook and Porridge
// Contest: Codeforces - Codeforces Round 935 (Div. 3)
// URL: https://codeforces.com/contest/1945/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
 
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}
 
LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
struct BIT{//Binary indexed Tree(树状数组)
	int n;
	vector<int> tr;
	BIT(int n) : n(n) , tr(n + 1 , 0){
	}
	int lowbit(int x){
		return x & -x;
	}
	void modify(int x , int modify_number){
		for(int i = x ; i <= n ; i += lowbit(i)){
			tr[i] += modify_number;
		}
	}
	void modify(int l , int r , int modify_number){
		modify(l , modify_number);
		modify(r + 1 , -modify_number);
	}
	int query(int x){
		int res = 0;
		for(int i = x ; i ;  i -= lowbit(i))
			res += tr[i];
		return res;
	}
	int query(int x , int y){
		return query(y) - query(x);
	}
};
struct Eat{//吃饭队列
	int ti;//归队时间
	int ss;//吃饭时间
	int id;//编号
	friend bool operator < (struct Eat a , struct Eat b){
		if(a.ti != b.ti){
			return a.ti > b.ti;
		}
		else{
			return a.ss > b.ss;
		}
	}
};
struct Rank{//就绪队列 优先级高的在前面,统一优先级到达时间晚的在后面
	int kk;//优先级
	int time;//到达时间
	int id;//编号
	int num;
	friend bool operator < (struct Rank a , struct Rank b){
		if(a.kk != b.kk){
			return a.kk < b.kk;
		}
		else if(a.time != b.time){
			return a.time > b.time;
		}
		else{
			return a.num > b.num;
		}
	}
};
void solve() 
{
	cin >> n >> m;
	pair<int,int>stu[n + 5];
	for(int i = 1 ; i <= n ; i ++){
		cin >> stu[i].x >> stu[i].y;
	}
	int num = 0;
	//怎么判断第i个人能否喝到粥？ -> 前面没有人
	//怎么计算第i个人第一次喝到粥的时刻？ -> 模拟时间
	//若第i个人会被插队的条件是,他之后没有比那个人优先级高的人了,之后加的也必然不会被卡
	vector<int>back(n + 5 , 0);//第i个人之后的最大优先,第i个人喝完之后,会在大于等于back[j]的后面,若没有,则放到第一个
	back[n + 1] = 0;
	for(int i = n ; i >= 1 ; i --){
		back[i] = max(back[i + 1] , stu[i].x);
	}
	priority_queue<Eat>e;//吃饭队列,时间到了归队
	priority_queue<Rank>r;//等待队列
	int id = 1;
	int ans = -1;
	for(int i = 1 ; i <= m ; i ++){
		if(r.empty() || back[id] >= r.top().kk){
			e.push({i + stu[id].y , stu[id].y , id});
			id++;
			if(id == n + 1){
				ans = i;
				break;
			}
		}
		else{
			int idx = r.top().id;
			r.pop();
			e.push({i + stu[idx].y , stu[idx].y , idx});
		}
		while(!e.empty() && e.top().ti == i){
			int idx = e.top().id;
			e.pop();
			r.push({stu[idx].x , i , idx , ++num});
		}
	}
	cout << ans << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}