[Codeforces673B]Problems for Round(思路,规律)

题目链接:http://codeforces.com/contest/673/problem/B

现在有n个题和m个相似的关系,现在要把他们分到2组去。

要求:

1组的所有题比2组难

每个组都得至少有一个题

两个问题相似的话,不能用在同一组

每个题只能用一次

特别注意的是,相似的关系是没有传递性的,也就是AB相似,BC相似,那AC不相似。

思路:由于每次输入的两个题一定不是一个div的,那我们规定每次都把小的放到2,大的放到1。并且维护2里的最大值和1里的最小值。仔细考虑一下就会发现正确的情况下不会出现2中的最大值大于1中的最小值的。而且用1中的最小值减去2中的最大值就是剩下了几个和其他几个都没关系的。假如l=5,r=8,那剩下了的就是6 7两个题。这两个题可以同时放到2也可以同时放到1,也可以6放到2、7放到1。所以他们的分配数为r-l=3。

注意如果r-l<0的话,那说明出现了交集,这些题是没法正常分配的。

 /*
━━━━━┒ギリギリ♂ eye!
┓┏┓┏┓┃キリキリ♂ mind!
┛┗┛┗┛┃\○/
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rlf(a) scanf("%llf", &a);
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define lrt rt << 1
#define rrt rt << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; const int maxn = ;
int n, m; int main() {
// FRead();
int u, v;
Rint(n); Rint(m);
int l = , r = n;
Rep(i, m) {
Rint(u); Rint(v);
if(u > v) swap(u, v);
l = max(u, l); r = min(v, r);
}
if(r - l < ) printf("0\n");
else printf("%d\n", r-l);
RT ;
}
上一篇:关于UrlEncode 一团乱麻的问题,后续彻底理解。Java中的 URLEncoder 与 URLDecoder无bug


下一篇:nor flash 和 nand flash