A - Orders
题意
每天能生产k个产品的工厂有n个订单，第i个订单是在a_i天交b_i个产品，问能否交付。
思路
订单按日期排序，记录剩下的商品.
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 1e6 + 5;
typedef pair<int, int> pii;
void solve()
{
int n, k;
scanf("%lld%lld", &n, &k);
vector<pii> v(n + 1);
v[0] = { 0,0 };
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld", &v[i].first, &v[i].second);
}
sort(v.begin(), v.end());
int sum = 0;
for (int i = 1; i <= n; i++)
{
sum += k * (v[i].first - v[i - 1].first);
sum -= v[i].second;
if (sum < 0)
{
printf("No\n");
return;
}
}
printf("Yes\n");
}
signed main()
{
int T = 1;
scanf("%lld", &T);
while (T--)
{
solve();
}
return 0;
}
D - Fast and Fat
题意
n个人，每个人有速度v和体重w，且每个人可以背一个人，当背的人的体重<=自己体重，速度不变，否则变为自己体重与二者体重差值之差，当差值<=0则代表不能背。总速度为每个单位速度的最小值，求团队最大速度。
思路
很明显的二分，二分速度，则第i个人能背上的人的最大体重为v_i - x + w_i(v_i - (w_i - w_j) == x)，选出速度>=x的人中v+w最大的人，分别去背着速度<=x的人中w最大的人。
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 1e6 + 5;
typedef pair<int, int> pii;
int n, l = LLONG_MAX, r = -1;
vector<pii> a, b;
bool cmp1(pii aa, pii bb)
{
return aa.second > bb.second;
}
bool cmp2(pii aa, pii bb)
{
return aa.first + aa.second > bb.first + bb.second;
}
bool check(int x)
{
queue<int> q, p;
// 被背的
for (int i = 0; i < n; i++)
{
if (a[i].first < x)
{
q.push(a[i].second);
}
}
// 背的
for (int i = 0; i < n; i++)
{
if (b[i].first >= x)
{
p.push(b[i].first + b[i].second - x);
}
}
// 背人的小于要被背的
if (p.size() < q.size())
{
return false;
}
//大的背小的
while (q.size())
{
if (p.front() < q.front()) // 背不了
{
return false;
}
p.pop();
q.pop();
}
return true;
}
void solve()
{
scanf("%lld", &n);
for (int i = 0; i < n; i++)
{
int v, w;
scanf("%lld%lld", &v, &w);
a.push_back({ v, w });
b.push_back({ v, w });
l = min(l, v);
r = max(r, v);
}
sort(a.begin(), a.end(), cmp1); // w大
sort(b.begin(), b.end(), cmp2); // (v + w)大的一定能背小的
while (l < r)
{
int mid = (l + r + 1) / 2;
if (check(mid))
{
l = mid;
}
else
{
r = mid - 1;
}
}
printf("%lld\n", l);
a.clear();
b.clear();
}
signed main()
{
int T = 1;
scanf("%lld", &T);
while (T--)
{
solve();
}
return 0;
}
E - Math Problem
题意
把n变成m的倍数，共两种操作：花费a使n = n * k + x ( 1 <= x <= k)，或，花费b使n = n / k并向下取整。求最小花费
思路
由于乘法操作中的x在[0, k)之间，并且除法操作向下取整，则如果先乘再除n就会不变。故可以一直做除法直到n = 0(0是任何数的倍数)，再在每次除法前进行乘法操作直至第一个m的倍数，更新ans。
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 1e6 + 5;
typedef pair<int, int> pii;
void solve()
{
int n, k, m, a, b;
scanf("%lld%lld%lld%lld%lld", &n, &k, &m, &a, &b);
if (n % m == 0)
{
printf("0\n");
return;
}
if (k == 1)
{
printf("-1\n");
return;
}
int ans = LLONG_MAX, cost = 0;
while (true)
{
int minn = n % m, l = 1, t = 0;
while (true) // 每次除之前乘，然后比较
{
if (l > (m - minn) % m) // 乘到第一个倍数
{
ans = min(ans, t + cost);
break;
}
t += a; // 当前乘法的消耗
minn = (minn * k) % m;
l *= k;
}
if (n == 0) // 除到0为止
{
printf("%lld\n", ans);
return;
}
// 除
n /= k;
cost += b;
}
}
signed main()
{
int T = 1;
scanf("%lld", &T);
while (T--)
{
solve();
}
return 0;
}
G -
题意
思路
I - Three Dice
题意
3个骰子，1、4为红面，其他为黑面。给定a，b，问是否有红面点数为a，黑面点数为b的情况。
思路
情况很少，直接列举Yes的情况。
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 1e6 + 5;
void solve()
{
int a, b;
scanf("%lld%lld", &a, &b);
if (a == 3 || a == 12 || a == 6 || a == 9) // 3红
{
printf((!b ? "Yes" : "No"));
return;
}
if (a == 2 || a == 8 || a == 5) // 2红
{
printf(b == 2 || b == 3 || b == 5 || b == 6 ? "Yes" : "No");
return;
}
if (a == 1 || a == 4) // 1红
{
for (int i = 2; i <= 6; i++)
{
if (i == 4)
{
continue;
}
for (int j = 2; j <= 6; j++)
{
if (j == 4)
{
continue;
}
if (i + j == b)
{
printf("Yes");
return;
}
}
}
}
if (a == 0) // 0红
{
for (int i = 2; i <= 6; i++)
{
if (i == 4)
{
continue;
}
for (int j = 2; j <= 6; j++)
{
if (j == 4)
{
continue;
}
for (int k = 2; k <= 6; k++)
{
if (k == 4)
{
continue;
}
if (i + j + k == b)
{
printf("Yes");
return;
}
}
}
}
}
printf("No");
}
signed main()
{
int T = 1;
//scanf("%lld", &T);
while (T--)
{
solve();
}
return 0;
}
L -
题意
思路
代码