Codeforces Round #727 (Div. 2)
比赛链接：https://codeforces.ml/contest/1539
A. Contest Start
题意：N个人参加比赛，间隔X分钟，比赛进行T分钟，求有多少人在当前人结束的时候还在跑步，求这个总和
题解：两类讨论，若时间不足则为等差数列求和否则为最大项*多出部分+等差数列求和
代码实现：
#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define endl ‘\n‘
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn = 3e5+10;
const int INF = 0x3f3f3f3f;
int fl[maxn];
signed main(){
fio;
int k,n,x,t;
cin >> t;
while(t--){
cin >> n >> x >> k;
int ans = 0;
int tmp = k/x;
if(n <= tmp) ans = (min(n,tmp) - 1) * min(n,tmp) / 2ll;
else ans = (tmp - 1) * tmp / 2ll + (n - tmp)*tmp;
cout << ans << endl;
}
return 0;
}
B. Love Song
题意：给字符串其中a-z分别重复1-26次，问L-R的长度
题解：前缀预处理
代码实现：
#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define endl ‘\n‘
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn = 3e5+10;
const int INF = 0x3f3f3f3f;
int ans[maxn];
signed main(){
fio;
int n,q;
string s;
cin >> n >> q;
cin >> s;
s = " " + s;
for(int i = 1;i <= n;i++){
ans[i] = ans[i-1] + s[i] - ‘a‘ + 1;
}
int l,r;
while(q--){
cin >> l >> r;
cout << ans[r] - ans[l - 1] << endl;
}
return 0;
}
C. Stable Group
题意：n个学生，每个学生能力值不同，对其进行分组使组内的能力差不大于x，此外老师还可以调入k个学生来辅助，问最少要分几组
题解：排序预分组，分好组后记录临组差值，之后计算之间需要插入多少学生,可以融合多少组
代码实现：
#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define endl ‘\n‘
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn = 3e5+10;
const int INF = 0x3f3f3f3f;
int a[maxn];
signed main(){
fio;
int n,x,k;
cin >> n >> k >> x;
for(int i = 1;i<=n;i++)cin >> a[i];
sort(a + 1,a + n + 1);
a[0] = a[1];
int cnt = 1;
vector<int>vc;
for(int i = 1;i <= n;i++){
if(a[i] - a[i-1] > x){
//cout << a[i] << "YY\n";
cnt++;
vc.push_back(a[i] - a[i-1]);
}
}
sort(vc.begin(),vc.end());
int cnt1 = 0;
for(int i = 0;i<vc.size();i++){
int tn = vc[i]/x + (vc[i] % x != 0) - 1;
if(tn <= k){
k -= tn;
cnt1++;
}else{
break;
}
}
cout << cnt - cnt1 <<endl;
return 0;
}
D. PriceFixed
题意：有n个物品，原价都是2元，第 i 个物品需要购买ai 件，当买bi 个物品时这个物品半价（这个是不限买哪个物品数量的）。问购买所需物品数量，最少需要花多少钱。
题解：贪心求解，双指针，从降价需求最多的拿物品来填补降价需求物品最少的货物
代码实现：
#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define endl ‘\n‘
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn = 3e5+10;
const int INF = 0x3f3f3f3f;
struct node{
int a,b;
}s[maxn];
int cmp(node x,node y){
if(x.b != y.b) return x.b < y.b;
else return x.a > y.a;
}
/*
2 3 4 5 6 7
4 6 7 9 11 12
*/
signed main(){
fio;
int n;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> s[i].a >> s[i].b;
}
sort(s + 1,s + n + 1,cmp);
int l = 1, r = n;
int tb = 0;
int ans = 0;
while(l <= r){
if(l == r){
if(tb > s[l].b){
ans += s[l].a;
}else if(tb + s[l].a > s[l].b){
int tn = s[l].b - tb;
s[l].a -= tn;
ans += tn * 2;
ans += s[l].a;
}else{
ans += s[l].a * 2;
}
break;
}
if(s[r].a + tb >= s[l].b){
int tn = s[l].b - tb;
if(tn < 0)tn = 0;
s[r].a -= tn;
ans += s[l].a;
tb = tb + s[l].a + tn;
s[l].a = 0;
ans += tn * 2;
l++;
}else{
tb += s[r].a;
ans += s[r].a * 2;
s[r].a = 0;
r--;
}
}
cout << ans <<endl;
return 0;
}