本文主要是介绍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;}elser = 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;//banvis[p[cnt - 1]] = 1;//outif(mp.count(p[cnt - 1])){//有了while(id <= n && vis.count(a[id].y)){id++;}minn = a[id].x;mp[a[id].y] = 1;id++;}//pickwhile(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
//
// Powered by CP Editor (https://cpeditor.org)#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;//编号friend bool operator < (struct Rank a , struct Rank b){if(a.kk != b.kk){return a.kk < b.kk;}else{return a.time > b.time;}}
};
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;}//怎么判断第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});}}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;
}
这篇关于Codeforces Round 935 (Div. 3) （A~G）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
