P2207 Photo

题目描述

Framer Jhon 打算给他的N头奶牛照相，( 2 <= N <= 1 000 000 000) 。

他们排成一条线，并且依次取1~N作为编号。

每一张照片可以拍摄到这列奶牛中一个连续的区间中的奶牛。

对于每一头奶牛，FJ都想要让Ta至少出现在一张照片里。

不幸的是，有K对关系不好的奶牛( 1 <= K <= 1000)，他们拒绝出现在同一张照片里。

已知所有关系不好的奶牛所在的位置，请计算出FJ需要的最小需要拍摄的照片数量。

输入输出格式

输入格式：

*第一行：两个整数: N,K.

*第2..K+1行中，第i+1行有两个整数，记为A_i与B_i。它们代表着处在队列中第A_i头奶牛与第B_i头奶牛是关系不好的，它们不能出现在同一张照片里。

输出格式：

*一个整数，代表FJ需要的最小需要拍摄的照片数量

最近在加油复习呢。加油加油！

由题意可知：两关系不好的奶牛中需要一个断点，由此转化为去最少的断点，使没一对关系不好的奶牛之间存在至少1断点，经典的贪心区间取点问题

此类区间取点问题的解法为区间排序。试想：在已经确定一个区间需要放置断点时，放在哪里最优呢？一定放在区间末尾，因为这样才能包含尽可能多的区间。所以我们对区间按照左端点进行排序，维护一个最后断点位置，当此区间的左端点 > 断点时，我们新放置一个断点在此区间的右端点处，符合贪心思想。

有一点需要注意的是区间包含问题，出现区间包含时，我们需要将最后断点的位置调整到小区间的右端点，以满足小区间中有断点。

还有一点要注意的是区间的开闭问题。像这题就是左闭右开类型的（奶牛不可能被切成两半，所以断点的定义确切的来说是上一张照片的结尾，所以区间使左闭右开）。建议统一使用闭区间写法（以确保正确然而代码力超强的大佬们根本不用管），用左右端点 \(+1,-1\) 来符合开闭即可。

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

typedef long long LL;

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 1019;

int num, nr;

struct Node{

	int l, r;

	}I[maxn];

bool cmp(Node a, Node b){

	if(a.l != b.l)return a.l < b.l;

	return a.r < b.r;

	}

int main(){

	num = RD(), nr = RD();

	for(int i = 1;i <= nr;i++){

		I[i].l = RD(), I[i].r = RD();

		if(I[i].l > I[i].r)swap(I[i].l, I[i].r);

		I[i].r--;//左闭右开处理一下

		}

	sort(I + 1, I + 1 + nr, cmp);

	int ans = 1, last = -1;

	for(int i = 1;i <= nr;i++){

		if(I[i].l > last){

			ans++;

			last = I[i].r;

			}

		else if(I[i].r < last)last = I[i].r;//区间包含处理

		}

	printf("%d\n", ans);

	return 0;

	}

巴特西

P2207 Photo

P2207 Photo

Code

最新文章

热门文章