9 条题解
-
3
本题考查点结构体排序以及贪心，不能使用冒泡排序，会超时。
题意简介：给你n个活动的起始时间和截至时间，任意两个活动的时间不能交叉，问你最优的安排可以完成几个活动。
解法：对各个活动的结束时间进行从小到大排序（画图理解一下）。然后判断后面的活动的起始时间是否大于上一个活动的结束时间， 满足的话说明这个活动可以完整举行。
#include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> using namespace std; const int N = 1e6 + 10; struct ch { int st, ed; }s[N]; bool cmp (ch a, ch b) { return a.ed < b.ed; } int main() { int t; scanf("%d", &t); while (t --) { int n; scanf("%d", &n); for (int i = 1;i <= n;i ++) { scanf ("%d %d",&s[i].st, &s[i].ed); } sort(s + 1,s + 1 + n, cmp); int ans = 1; int last = s[1].ed; for (int i = 2; i <= n;i ++) { if (last < s[i].st) { ans ++; last = s[i].ed; } } printf("%d\n",ans); } } -
2
#include<bits/stdc++.h> using namespace std; struct huodong { int bi;//开始时间 int ei;//结束时间 }; bool paixu (huodong b, huodong e)//布尔类型 { return b.ei < e.ei; } int main() { int t,sum; cin>>t; while(t--) { sum = 1; int n; cin>>n; huodong hd[n]; for(int i=0;i<n;i++)//对活动开始停止时间进行赋值 { cin>>hd[i].bi; cin>>hd[i].ei; } sort(hd,hd+n,paixu); int temp = hd[0].ei; for(int i=1;i<n;i++) { if(temp<hd[i].bi) { sum++; temp = hd[i].ei; } } cout<<sum<<endl; } } -
2
ShuBingHai LV 10 @ 2023-10-7 20:04:31
//练习的结构体和sort排序 #include <algorithm> #include <iostream> using namespace std; struct huiChangtimes { int start; int end; }; bool zhengXu(huiChangtimes a, huiChangtimes b) { return a.end < b.end; } int main() { int m = 0; cin >> m; for (int i = 0; i < m; i++) { int n = 0; cin >> n; huiChangtimes tim[n]; for (int j = 0; j < n; j++) { cin >> tim[j].start >> tim[j].end; } sort(tim, tim + n, zhengXu); int times = 1; int lasttimes = tim[0].end; for (int j = 1; j < n; j++) { if (lasttimes < tim[j].start) { times++; lasttimes = tim[j].end; } } cout << times << endl; } } -
2
python大法好，拒绝手写结构体排序，从我做起（实际上是py自带的关键字排序）。
m = int(input()) for _ in range(m): n = int(input()) act = [] act_num = 1 for __ in range(n): lst = list(map(int, input().split( ))) act.append(lst) act.sort(key = lambda x : x[1]) pointer = 0 for i in range(1, n): if act[i][0] > act[pointer][1]: act_num += 1 pointer = i print(act_num) -
1
2787620039 LV 9 @ 2024-11-22 19:38:55
还是用c语言，只不过借用c++的一个排序函数提交的时候把c改为c++提交。
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef struct S{
int a;
int b;
}s;
bool ak47(s x,s y){
return x.b<y.b;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
s ar[n];
for(int i=0;i<n;i++){
scanf("%d %d",&ar[i].a,&ar[i].b);
} sort(ar,ar+n,ak47);
int sum=1;
int al=ar[0].b;
for(int i=1;i<n;i++){
if(al<ar[i].a){
sum++;
al=ar[i].b;
}
} printf("%d\n",sum);
}
return 0;
}
-
0
C的写法，使用了qsort进行排序,也因此需要写出相应的比较函数
#include <stdio.h> #include <stdlib.h> typedef struct Activity{ int start; int end; } Activity; Activity activity[10000]; int n; int ans; void init() { int s,e; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &s, &e); activity[i].start = s; activity[i].end = e; } } int cmp(const void *a, const void *b) { Activity *x = (Activity *)a; Activity *y = (Activity *)b; if (x->end == y->end) { return x->start - y->start; } else { return x->end - y->end; } } void solve() { qsort(activity, n, sizeof(Activity), cmp); ans = 1; int last = activity[0].end; for (int i = 1; i < n; i++) { if (activity[i].start >= last + 1) { ans++; last = activity[i].end; } } printf("%d\n", ans); } int main() { int m; scanf("%d", &m); for (int i = 0; i < m; i++) { init(); solve(); } return 0; }
以下为qsort函数原型
void qsort( void *base, // 待排序数组的首地址（任意类型指针） size_t nmemb, // 数组中元素的个数 size_t size, // 每个元素的大小（单位：字节） int (*compar)(const void *, const void *) // 比较函数指针 ); -
0
#include<cstdio> #include<algorithm> using namespace std; struct Activity { int start; int end; }; bool cmp(Activity a, Activity b) { return a.end < b.end;//结束时间小的在左边的意思 } int main() { int m,n; scanf("%d",&m); while(m--)//m组 { scanf("%d",&n);//n个活动 Activity activities[10001]; // 使用结构体数组 // 读取所有活动 for(int i=0;i<n;i++) { scanf("%d%d",&activities[i].start, &activities[i].end); } // 按结束时间排序 sort(activities, activities + n, cmp); int count = 0; int lasttime = -1; for(int i=0;i<n;i++) { if(lasttime < activities[i].start) { count++; lasttime = activities[i].end; } } printf("%d\n",count); } return 0; } -
0
确实巧妙。 不想创建结构体的同学也可以选择c++的piar类来替代此处的自定义结构体。 不知道为什么，没办法上传代码块，上传代码块会更新错误。 下为代码： #include<iostream> #include<vector> #include<utility> #include<algorithm> using namespace std; template<class T> class Less { public: bool operator()(const T& a , const T& b) { return a.second < b.second; } }; int main() { int m; cin >> m; while(m--) { int n; cin >> n; vector<pair<int , int>> _v(n); for(int i = 0 ; i < n ; i++) { cin >> _v[i].first >> _v[i].second; } sort(_v.begin() , _v.end() , Less<pair<int , int>>()); int ret = 1; int comp = _v[0].second; for(int i = 1 ; i < n ; i++) { if(comp < _v[i].first) { ret++; comp = _v[i].second; } } cout << ret << endl; } return 0; }
-
0
rust_not_love_me LV 6 @ 2023-8-26 23:48:20
参考VAC，给出rust实现。
use std::io::{self, BufRead}; fn main() { let stdin = io::stdin(); let mut lines = stdin.lock().lines().map(|line| line.unwrap()); let m: i32 = lines.next().unwrap().parse().unwrap(); for _ in 0..m { let n: usize = lines.next().unwrap().parse().unwrap(); let mut activities = Vec::new(); // 读取每个活动的起始时间和结束时间 for _ in 0..n { let line = lines.next().unwrap(); let split: Vec<i32> = line .split_whitespace() .map(|x| x.parse().unwrap()) .collect(); activities.push(split); } // 按照结束时间升序排序 activities.sort_by(|a, b| a[1].cmp(&b[1])); let mut act_num = 1; // 已安排的活动数量 let mut pointer = 0; // 指向上一个活动的索引 // 从第二个活动开始，检查是否与前一个活动时间冲突 for i in 1..n { if activities[i][0] > activities[pointer][1] { // 没有时间冲突，可以安排该活动 act_num += 1; pointer = i; } } println!("{}", act_num); // 输出结果 } }
ZIFEI
LV 10
MOD
@ 2023-8-21 20:14:44
- 1