贪心 吃糖
https://codeforces.com/problemset/problem/436/A
题意
有那么个怪物，要吃糖，糖果有两种1和0，每颗糖有一个高度，怪物吃了糖会获得对应的能量，而怪物有个初始能量值可以保证怪物的跳起吃糖，且怪物很作，吃糖要交替着吃。现在问，怪物最多能吃到几颗糖
解题思路：贪心，对糖果的能量从高到低进行排序，然后，每次都去吃能吃到的能量最高的糖果，这样可以保证能吃到最多的糖果，先吃1和0的结果会有不同，所以要分情况讨论
AC代码
#include #include #include #include using namespace std;const int maxn = 2e3 + 10;#define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);struct node {int t, h, m;}A[maxn],B[maxn];bool cmp(node a,node b){if(a.m == b.m)return a.h < b.h;elsereturn a.m > b.m;}int sum1, sum2;int main(){IOS;int n, x;cin >> n >> x;int t, h, m;for(int i = 1;i <= n;++ i){cin >> t >> h >> m;A[i].t = t;A[i].h = h;A[i].m = m;B[i].t = t;B[i].h = h;B[i].m = m;}sort(A+1,A+n+1,cmp);sort(B+1,B+n+1,cmp);int flag1 = 0,flag2 = 1;int power1 = x, power2 = x;for(int i = 1;i <= n;++ i){if(power1 >= A[i].h && A[i].t == flag1){power1 += A[i].m;sum1 ++;A[i].t = -1;flag1 = 1 - flag1;i = 0;}} for(int i = 1;i <= n;++ i){if(power2 >= B[i].h && B[i].t == flag2){power2 += B[i].m;sum2 ++;B[i].t = -1;flag2 = 1 - flag2;i = 0;}} int ans = max(sum1, sum2);cout << ans ;return 0;}
区间合并
给定 n 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例：
51 22 45 67 87 9
输出样例：
3
AC代码
#include using namespace std;typedef pair PII;int n;vector query;int main(){ cin >> n; for (int i = 0; i < n; i ++ ) { int l, r; cin >> l >> r; query.push_back({l, r}); } sort(query.begin(), query.end()); int cnt = 0, st = -2e9; for (auto item : query) { if (item.first > st) cnt ++ ; st = max(st, item.second); } cout << cnt << endl; return 0;}
区间分组
给定 N 个闭区间 [ai,bi][ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3-1 12 43 5
输出样例：
2
AC思路
AC代码
#include #include #include #include using namespace std;const int N = 100010;int n;struct Range{ int l, r; bool operator< (const Range &W)const { return l < W.l; }}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); priority_queue, greater> heap; for (int i = 0; i < n; i ++ ) { if (heap.empty() || heap.top() >= range[i].l){ heap.push(range[i].r); } else { heap.pop(); heap.push(range[i].r); } } printf("%dn", heap.size()); return 0;}
区间覆盖
给定 N 个闭区间 [ai,bi][ai,bi] 以及一个线段区间 [s,t][s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
输入格式
第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。
第二行包含整数 N，表示给定区间数。
接下来 N行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出 −1。
数据范围
1≤N≤105,
−109≤ai≤bi≤109,
−109≤s≤t≤109
输入样例：
1 53-1 32 43 5
输出样例：
2
AC思想
AC代码
#include #include using namespace std;const int N = 100010;int n;struct Range{ int l, r; bool operator< (const Range &W)const { return l < W.l; }}range[N];int main(){ int st, ed; scanf("%d%d", &st, &ed); 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; bool success = false; for (int i = 0; i < n; i ++ ) { int j = i, r = -2e9; while (j < n && range[j].l <= st) { r = max(r, range[j].r); j ++ ; } if (r < st) { res = -1; break; } res ++ ; if (r >= ed) { success = true; break; } st = r; i = j - 1; } if (!success) res = -1; printf("%dn", res); return 0;}
区间选点
给定 N 个闭区间 [ai,bi][ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3-1 12 43 5
输出样例：
2
AC代码
#include #include using namespace std;const int N = 100010;int n;struct Range{ int l, r; bool operator< (const Range &W)const { return r < W.r; }}range[N];int main(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r); sort(range, range + n); int res = 0, ed = -2e9; for (int i = 0; i < n; i ++ ) if (range[i].l > ed) { res ++ ; ed = range[i].r; } printf("%dn", res); return 0;}
最大不相交区间数量
给定 N 个闭区间 [ai,bi][ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3-1 12 43 5
输出样例：
2
AC代码
#include #include using namespace std;const int N = 100010;int n;struct Range{ int l, r; bool operator< (const Range &W)const { return r < W.r; }}range[N];int main(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r); sort(range, range + n); int res = 0, ed = -2e9; for (int i = 0; i < n; i ++ ) if (ed < range[i].l) { res ++ ; ed = range[i].r; } printf("%dn", res); return 0;}