[USACO 2009 Dec S]Selfish Grazing

Consider a set of 5 cows with ranges shown below: ... 1 2 3 4 5 6 7 8 9 10 11 12 13 ... ... |----|----|----|----|----|----|----|----|----|----|----|----|---- Cow 1: <===:===> : : : Cow 2: <========:==============:==============:=============>: Cow 3: : <====> : : : Cow 4: : : <========:===> : Cow 5: : : <==> : : These ranges represent (2, 4), (1, 12), (4, 5), (7, 10), and (7, 8), respectively. For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.

pypy3(pypy3.6.1) 解法, 执行用时: 300ms, 内存消耗: 28120K, 提交时间: 2020-05-16 00:44:36

import io, os
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
R = lambda : map(int, input().split())
n = int(input())
a = [tuple(R()) for _ in range(n)]
a.sort(key=lambda x:x[1])
l, r = a[0]
ans = 1
for i in a[1:] :
    if r <= i[0] :
        ans += 1
        l, r = i
print(ans)

C++ 解法, 执行用时: 39ms, 内存消耗: 808K, 提交时间: 2021-10-09 21:34:19

#include<bits/stdc++.h>
using namespace std;
int N, a, p;
pair<int, int>s[50009]; 
int main()
{
	cin >> N;
	for(int i = 0; i < N; i++)
		cin >> s[i].second >> s[i].first;
	sort(s, s+N);
	for(int i = 0; i < N; i++)
		if(s[i].second >= p)
			a ++, p = s[i].first;
	cout << a;
}

Python3(3.5.2) 解法, 执行用时: 187ms, 内存消耗: 14140K, 提交时间: 2020-07-24 10:45:03

n=int(input())
a=[[int(i) for i in input().split()]for j in range(n)]
a.sort(key=lambda x:x[1])
sum=0
end=-1
for i in range(n):
    if a[i][0]>=end:
        sum+=1
        end=a[i][1]
print(sum)

详情