原题链接:https://www.acwing.com/activity/content/problem/content/7305/(AcWing 4500. 三个元素)
map:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
map<int, int> pos;
for (int i = 1; i <= n; i ++ )
{
int x;
cin >> x;
pos[x] = i; //map的初始化
}
if (pos.size() < 3) puts("-1 -1 -1");
else
{
vector<int> res;
for (auto [k, v]: pos) res.push_back(v);
for (int i = 0; i < 3; i ++ )
cout << res[i] << ' ';
cout << endl;
}
return 0;
}
//by yxc
vector< pair < int, int > >:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 3010;
vector<PII> a;
void qsort(int l, int r) //手打快排 :D
{
if(l >= r) return ;
int mid = (l + r) / 2, i = l - 1, j = r + 1;
while(i < j)
{
do i ++ ;while(a[i].first < a[mid].first);
do j -- ;while(a[j].first > a[mid].first);
if(i < j)
{
int f1, s1;
f1 = a[i].first;
s1 = a[i].second;
a[i].first = a[j].first;
a[i].second = a[j].second;
a[j].first = f1;
a[j].second = s1;
}
}
qsort(l, j);
qsort(j + 1, r);
}
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++ )
{
int x;
cin >> x;
a.push_back({x, i});
}
qsort(0, n - 1); //排序
int cnt = 1; //去重
for(int i = 1; i < n; i ++ )
{
if(a[i].first != a[i - 1].first)
{
a[cnt].first = a[i].first; //访问第一个用first
a[cnt].second = a[i].second; //访问第二个用second
cnt ++ ;
}
}
if(cnt >= 3)
{
for(int i = 0; i < 3; i ++ )
cout << a[i].second << " ";
}
else cout << "-1 -1 -1";
return 0;
}
用sort排序的话会根据第一个大小排序,也就是first大小
905. 区间选点
//区间问题都是需要排序的,在这里按照左端点从小到大排序
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
typedef pair<int, int>PII;
PII range[N];
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r};
}
sort(range, range+ n);
int res = 0, INF = -2e9+7;
for(int i = 0; i < n; i++){
if(range[i].first > INF){
res++;
INF = range[i].second;
}else{
INF = min(INF, range[i].second);
}
}
printf("%d\n", res);
return 0;
}