Codeforces Round_(rated,Div.2,based on VK Cup 2018 Round 3)ABC

5237 ワード

Codeforces

A.Mind the Gap
転送ゲート:http://codeforces.com/contest/967/problem/A
タイトルの大意:
n個の飛行機の着陸時間と時間差を与えて、離陸と着陸には1分間かかります.つまり時間差はs＋1です.今はもう一つの飛行機の出発時間を挿入します.このn＋1時間はまだ二つの間のs＋1分の差を維持します.
ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define P pair
#define ll long long
#define INF 100000000
#define M 1e9+7
#define MAX 500010
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
using namespace std;

int n, t, ansh, anss;
int h[110], s[110];

int main()
{
	cin >> n >> t;
	for (int i = 0; i < n; i++)
		cin >> h[i] >> s[i];

	ansh = 0; anss = 0;
	for (int i = 0; i < n; i++) {
		if ((h[i] - ansh) * 60 + s[i] - anss >= t + 1)
			break;
		anss = s[i] + t + 1;
		ansh = h[i];
		if (anss >= 60) {
			ansh += anss / 60;
			anss -= (anss / 60) * 60;
		}
	}
	cout << ansh << ' ' << anss << endl;
	return 0;
}

B.Watering System
転送ゲート:http://codeforces.com/contest/967/problem/B
タイトルの大意:
一つの水道管はn個の穴があります.穴の大きさはそれぞれs 1、s 2…snです.Aリットルの水を入れると、各穴から(si＊A)／Sリットルの水が流れ出ます.その中のSは穴の大きさの和です.すみません、一番目の穴から少なくともBリットルの水が流れ出ます.(明らかに最初の穴は閉じられていません)
考え方:
最初の穴から出る水は(s 1＊A)／Sです.中にはSだけが変化します.順番を決めて最大の初めから封じればいいです.
ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define P pair
#define ll long long
#define INF 100000000
#define M 1e9+7
#define MAX 500010
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
using namespace std;

int n;
int a, b;
int s[100010];

bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	cin >> n >> a >> b;
	int tot = 0;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		tot += s[i];
	}
	int first_h = s[0];
	sort(s, s + n, cmp);

	int left = first_h*a / tot;
	int cnt = 0;
	bool judge = false;
	while (left < b) {
		if (!judge) {
			if (s[cnt] == first_h) {
				cnt++;
				judge = true;
				continue;
			}
		}
		tot -= s[cnt++];
		left = first_h*a / tot;
	}
	if (judge)
		cnt--;
	cout << cnt << endl;
	return 0;
}

C.Stirs and Elevators
転送ゲート:http://codeforces.com/contest/967/problem/C
タイトルの大意:
n*mのビルには階段とエレベーターがあり、それぞれclとceの列に分布しています.階段は1階ごとに1つの時間単位がかかります.エレベーターはvビルを歩くごとに1つの時間単位がかかります.もちろん同じ階で左右に1つの時間単位がかかります.問(x 1,y 1)から(x 2,y 2)までの最短時間はいくつかの時間単位が必要ですか?
考え方:
同じ階ではない場合は、階段とエレベーターをそれぞれ一回計算して最小値を求めます.垂直方向の距離は直接abs(y 2-y 1)です.もし横の階段/エレベーターがx 1とx 2の間にあるならば、距離はabs(x 2-x 1)で、そうでなければx 1から一番近い階段/エレベーターを選んでください.距離はdであると仮定して、距離はabs(x 2-x 1)+2*dです.
同じ階にいるなら、階段やエレベーターを探さずにまっすぐ行けばいいです.
ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define P pair
#define ll long long
#define INF 1e9
#define M 1e9+7
#define MAX 500010
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
using namespace std;

int n, m, c1, c2, v, q;
int stair[100010], elevator[100010];

int main()
{
	cin >> n >> m >> c1 >> c2 >> v;
	for (int i = 0; i < c1; i++)
		scanf("%d", &stair[i]);
	for (int i = 0; i < c2; i++)
		scanf("%d", &elevator[i]);

	cin >> q;
	int x1, y1, x2, y2;
	int ans1, ans2;
	while (q--) {
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		int temp = min(x1, x2);
		x2 = max(x1, x2); x1 = temp;
		temp = min(y1, y2);
		y2 = max(y1, y2); y1 = temp;

		if (x1 == x2) {
			cout << y2 - y1 << endl;
			continue;
		}
		ans1 = 0; ans2 = 0;

		int pos = lower_bound(stair, stair + c1, y1) - stair;
		if (pos != c1&&stair[pos] <= y2)
			ans1 += y2 - y1;
		else {
			int a1 = INF, a2 = INF;
			if (pos != 0)
				a1 = y1 - stair[pos - 1];
			pos = lower_bound(stair, stair + c1, y2) - stair;
			if (pos != c1)
				a2 = stair[pos] - y2;
			ans1 += y2 - y1 + 2 * min(a1, a2);
		}
		ans1 += x2 - x1;

		pos = lower_bound(elevator, elevator + c2, y1) - elevator;
		if (pos != c2&&elevator[pos] <= y2)
			ans2 += y2 - y1;
		else {
			int a1 = INF, a2 = INF;
			if (pos != 0)
				a1 = y1 - elevator[pos - 1];
			pos = lower_bound(elevator, elevator + c2, y2) - elevator;
			if (pos != c2)
				a2 = elevator[pos] - y2;
			ans2 += y2 - y1 + 2 * min(a1, a2);
		}
		ans2 += (x2 - x1) / v;
		if ((x2 - x1) % v != 0)
			ans2++;

		cout << min(ans1, ans2) << endl;
	}

	return 0;
}

NodeJs簡明教程(4)