本篇题解只是记录我的做题过程代码,不提供最优解
(另外这里所有的时间复杂度都只分析单个样例,不算$t$的时间复杂度)
A
点击此处查看对应的题目.
本题设计算法:模拟
特判掉 1 的两种情况后,先把共同部分的差值乘2,剩余部分分成奇数偶数讨论(因为从起点到终点往往有两种做法)
时间复杂度 $O(1)$
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
typedef pair<char ,string> PCS;
void solve()
{
int n,m;
cin >> n >> m;
if (n == 1 && m == 1) {
puts("0");
}else if ((n == 1 || m == 1)) {
if (abs(n - m) != 1) puts("-1");
else puts("1");
}else {
if ((max(n,m) - min(n,m)) & 1) cout << (min(n,m) - 1) * 2 + (max(n,m) - min(n,m)) * 2 - 1<< '\n';
else cout << (min(n,m) - 1) * 2 + (max(n,m) - min(n,m)) * 2 << '\n';
}
}
int main()
{
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
B
点击此处查看对应的题目.
本题设计算法:贪心
贪心策略:从大到小地让人坐下,除了第一个人需要算两边的位置以外,其他人就只要算1边的位置,最后看位置够不够坐即可。
时间复杂度 $O(nlogn)$
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
typedef pair<char ,string> PCS;
int a[N];
void solve()
{
int n,m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
sort(a + 1,a + n + 1);
for (int i = n;i >= 1;i -- ) {
if (m <= 0) {
cout << "NO" << '\n';
return;
}
if (i == n) m -= 2 * a[i] + 1;
else m -= a[i] + 1;
}
cout << "YES" << '\n';
}
int main()
{
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
C
点击此处查看对应的题目.
本题设计算法:模拟 + 贪心
有数据范围我们可以得知本题可以暴力,有样例显示,再生成的数列种必然有1个正递增数列和负递减数列,其中间必为0。所以我们可以 枚举中间 0 的所在位置,然后向两边贪心的生成递增数列。
贪心策略:尽可能少的用 a[i] 改变 b[i] 的值。
时间复杂度 $O(n^2)$
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10,INF = 1e18;
typedef pair<char ,string> PCS;
ll a[N],b[N];
ll res = INF;
int main()
{
int n;
cin >> n;
for (int i = 1;i <= n;i ++ ) cin >> a[i];
for (int i = 1;i <= n;i ++ ) {
for (int j = 1;j <= n;j ++ ) b[j] = 0;
b[i] = 0;
ll k = 0;
for (int j = i - 1;j >= 1;j -- ) {
ll val1 = abs(b[j + 1]),val2 = abs(a[j]);
ll t = (val1 + 1) / val2 + ((val1 + 1) % val2 ? 1 : 0);
if (!t) k ++;
else k += t;
b[j] = -(t * val2);
}
for (int j = i + 1;j <= n;j ++ ) {
ll t = (b[j - 1] + 1) / a[j] + ((b[j - 1] + 1) % a[j] ? 1 : 0);
if (!t) k ++;
else k += t;
b[j] = (t * a[j]);
}
res = min(res,k);
}
cout << res << '\n';
return 0;
}