水 A - Wilbur and Swimming Pool
自从打完北京区域赛,对矩形有种莫名的恐惧..
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f; int main(void) {
int n, x[4], y[4];
cin >> n;
for (int i=0; i<n; ++i) {
cin >> x[i] >> y[i];
}
if (n == 1) puts ("-1");
else if (n == 2) {
if (x[0] == x[1] || y[0] == y[1]) puts ("-1");
else {
int ans = abs (x[0] - x[1]) * abs (y[0] - y[1]);
cout << ans << endl;
}
}
else if (n == 3) {
int ans = -1;
if (x[0] == x[1]) {
ans = abs (y[0] - y[1]) * abs (x[2] - x[0]);
}
else if (x[0] == x[2]) {
ans = abs (y[0] - y[2]) * abs (x[1] - x[0]);
}
else if (x[1] == x[2]) {
ans = abs (y[1] - y[2]) * abs (x[0] - x[1]);
}
cout << ans << endl;
}
else {
int ans = -1;
if (x[0] == x[1]) {
ans = abs (y[0] - y[1]) * abs (x[2] - x[0]);
}
else if (x[0] == x[2]) {
ans = abs (y[0] - y[2]) * abs (x[1] - x[0]);
}
else if (x[0] == x[3]) {
ans = abs (y[0] - y[3]) * abs (x[1] - x[0]);
}
cout << ans << endl;
} return 0;
}
贪心(水) B - Wilbur and Array
直接扫一边,记录后面的值.忘开long long
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
ll a[N]; int main(void) {
int n; cin >> n;
for (int i=1; i<=n; ++i) {
cin >> a[i];
}
ll ans = 0;
ll now = 0, oth = 0;
for (int i=1; i<=n; ++i) {
now = oth;
if (now == a[i]) continue;
else if (now < a[i]) {
ll tmp = a[i] - now;
oth += tmp;
ans += tmp;
}
else {
ll tmp = now - a[i];
oth -= tmp;
ans += tmp;
}
}
cout << ans << endl; return 0;
}
贪心+排序 C - Wilbur and Points
题意:给出n个点以及n个w[i],问一个点的序列,使得w[i] = p[j].y - p[j].x,并且保证不出现p[i].x <= p[j].x && p[i].y <= p[j].y (i > j)
分析:其实就是到水题,map映射下,用set + pair来存储点,自动从小到大排序,最后再判序列是否满足题意.tourist的判断代码好神奇,一直怀疑自己读错题,应该是能查看数据的吧.
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
map<int, set<pair<int, int> > >mp;
int w[N];
pair<int, int> ans[N]; int main(void) {
int n; scanf ("%d", &n);
for (int x, y, i=1; i<=n; ++i) {
scanf ("%d%d", &x, &y);
mp[y-x].insert (make_pair (x, y));
}
for (int i=1; i<=n; ++i) {
scanf ("%d", &w[i]);
}
for (int i=1; i<=n; ++i) {
if (mp[w[i]].empty ()) {
puts ("NO"); return 0;
}
ans[i] = *(mp[w[i]].begin ());
mp[w[i]].erase (mp[w[i]].begin ());
}
for (int i=2; i<=n; ++i) {
int x1 = ans[i].first, x2 = ans[i-1].first;
int y1 = ans[i].second, y2 = ans[i-1].second;
if (x1 <= x2 && y1 <= y2) {
puts ("NO"); return 0;
}
}
puts ("YES");
for (int i=1; i<=n; ++i) {
int x = ans[i].first;
int y = ans[i].second;
printf ("%d %d\n", x, y);
} return 0;
}