NC24447. [USACO 2014 Dec B]Cow Jog
描述
输入描述
The first line of input contains the integer N.
The following N lines each contain the initial position and speed of a
single cow. Position is a nonnegative integer and speed is a positive
integer; both numbers are at most 1 billion. All cows start at
distinct positions, and these will be given in increasing order in
the input.
输出描述
A single integer indicating how many groups remain.
示例1
输入:
5 0 1 1 2 2 3 3 2 6 1
输出:
2
C++14(g++5.4) 解法, 执行用时: 100ms, 内存消耗: 1380K, 提交时间: 2020-04-11 13:18:41
#include <bits/stdc++.h>
using namespace std;
typedef struct ss{
int x,y;
}ss;
bool cmp(ss a,ss b){
return a.x>b.x;
}
int main(){
int n;
cin>>n;
vector<ss> a(n);
for(int i=0;i<n;i++)
cin>>a[i].x>>a[i].y;
sort(a.begin(),a.end(),cmp);
int N=1,M=a[0].y;
for(int i=1;i<n;i++)
if(a[i].y<=M){
N++;
M=a[i].y;
}
cout<<N;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 64ms, 内存消耗: 764K, 提交时间: 2020-04-12 20:32:28
#include<bits/stdc++.h>
using namespace std;
int n,x,ans,maxx=1e9,a[100005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d %d",&x,a+i);
for(int i=n;i>=1;i--){
if(a[i]<=maxx){
ans++;
maxx=a[i];
}
}
printf("%d",ans);
}