B. Find The Array
对于条件二来说,1 是万金油的存在,所以我们只需要把奇数位置或偶数位置全部变成 1 即可。因为要求差值小于\(\frac s 2\),所以我可以求出奇偶位的和修改较小值即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
constexpr int inf = 1e9;
void solve(){
int n;
cin >> n;
vector<int> a(n);
for( auto &i : a ) cin >> i;
int x = 0 , y = 0 , t ;
for( int i = 0 ; i < n ; i ++ ){
if( i & 1 ) x += a[i];
else y += a[i];
}
t = x <= y;
for( int i = 0 ; i < n ; i ++ ){
if( (i&1) == t ) cout << "1 ";
else cout << a[i] << " ";
}
cout << "\n";
return ;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t;
for( cin >> t ; t ; t -- )
solve();
return 0;
}
C. Busy Robot
模拟即可,要注意满足要求的判定条件。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
void solve() {
int n;
cin >> n;
vector<int> t(n + 2), x(n + 2);
for (int i = 1; i <= n; i++)
cin >> t[i] >> x[i];
t[n + 1] = inf;
int startT = 0, endT = 0, startX = 0, endX = 0, res = 0;
for (int i = 1; i <= n; i++) {
if (t[i] >= endT) {
startX = endX, endX = x[i];
startT = t[i], endT = startT + abs(endX - startX);
if (endT <= t[i + 1]) {
res++;
}
} else {
int d = (endX - startX) / abs(endX - startX);
int lx = startX + d * (t[i] - startT), rx = startX + d * (min( endT , t[i + 1]) - startT);
if (lx > rx) swap(lx, rx);
if (((x[i] > startX) == (endX > startX)) and lx <= x[i] and x[i] <= rx) {
res++;
}
}
}
cout << res << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
for (; t; t--)
solve();
return 0;
}
D. Pairs
这道题其实可以贪心的做,只要求出\(x\)的最大值和最小值即可。现在的问题是如何求出最值?其实一个比较简单的做法是,直接进行贪心的匹配,优先给较小值匹配一个更大的数,这样就可以知道\(x\)的最大值。反过来操作就是最小值。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
using vi = vector<int>;
#define mp make_pair
constexpr int inf = 1e18;
void solve() {
int n;
cin >> n;
vi v(2 * n + 1);
for (int i = 1, x; i <= n; i++)
cin >> x, v[x] = 1;
int l = 0, r = n;
for (int i = 1, cnt = 0; i <= n * 2; i++) {
if (v[i]) {
if (cnt) cnt--;
else l++;
} else cnt++;
}
for (int i = n * 2, cnt = 0; i >= 1; i--) {
if (v[i]) {
if (cnt) cnt--;
else r--;
} else cnt++;
}
cout << r - l + 1 << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t;
for (cin >> t; t; t--)
solve();
return 0;
}
标签:Educational,int,Codeforces,long,--,solve,startX,using,100
From: https://www.cnblogs.com/PHarr/p/17705567.html