洛谷-线段覆盖-(区间排序问题总结)

P1803

题意：
就是有n个会议，每个会议有一个起始时间和终止时间。一个会议必须等前一个会议结束才能开始，现在问你最多可以安排多少会议。

思考：
1.如果dp做多了，想定义dp[i]为到第i个会议，最多可以选的会议个数，要么当前不选，要么选从一个不冲突的来转移，但是这样复杂度n*log(n)，因为你找转移点的时候要二分找出最近的r<=当前l的。
2.如果考虑贪心，我们需要选出最多的不相交的时间段，可以尝试以下的贪心策略：
每次从剩下未安排会议中选出最早开始且与已安排会议不冲突的会议。
每次从剩下未安排会议中选出持续时间最短且与已安排会议不冲突的会议。
每次从剩下未安排会议中选出最早结束且与已安排会议不冲突的会议。
3.如果选择最早开始时间，如果会议持续时间很长，假如7点开始，却要持续24小时，这样每天只能安排一个会议，肯定不合理。如果选择持续时间最短，则可能开始时间很晚，也不合理。因此我们最好选择开始最早而且结束时间短的会议，即最早开始时间+持续时间最短，这不就等价于选最早结束时间嘛！因此，我们采用第3种贪心策略。
4.所以按右端点从小到大排序就可以了，能选就选。可能回想，如果我不选第一个，去选第二个会不会更优？不会，假如第一个的结束时间是2，第二个是4，为啥我不选择一个结束时间更早的呢？。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e6+10,M = 2010;

int T,n,m,k;
PII va[N];

bool cmp(PII A,PII B)
{
	return A.se<B.se;
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
	sort(va+1,va+1+n,cmp);
	int ed = va[1].se,sum = 1;
	for(int i=2;i<=n;i++)
	{
		if(va[i].fi>=ed)
		{
			sum++;
			ed = va[i].se;
		}
	}
	cout<<sum;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

杭电多校-Package Delivery

题意：
就是给你n个包裹，每个包裹可以在第L天到第R天去拿，每次可以从邮局拿最多k个包裹。问你小明最少要跑多少次邮局可以全部拿完。

思考：
1.刚开始我以为是按左端点排序，然后每次尽量拿，看看能拿多少，然后次数就加上包裹/k。但是这样会亏，第一次可能拿3个要跑两次，不如第一次拿2个，第二次再拿两个。所以按左端点排序不行，而且枚举到i的时候，这个i当前不是必拿的，因为他还有r，所以可以在后面拿。
2.所以考虑，按右端点从小到大排序，这样枚举到i的时候，这个点必须要拿，在拿他的同时，尽量把后面的能拿的都拿。比如k = 2，但是如果此时能拿7个，我拿几个？
3.如果全部拿完，7个要拿3次，有点亏，肯定让其中一个扔给后面。
4.如果拿k的倍数个，也就是6个。看起来挺贪心的，一个都不浪费。实际上，如果后面还有必拿的区间，完全可以当前就拿m个，剩下的都给后面必拿的去补上就好了。
5.所以对于当前，我就拿最多m个。多的那些，当然我可以拿，但是他们也可以自己拿呀，所以尽量先不拿，先扔给后面，如果最后谁都拿不了了，那就自己拿。
6.然后就是如何实现，比如枚举到i，那么拿了自己，还可以拿m-1个，所以要从后面找出va[x].fi<=va[i].se的。找出来m-1个，如果有100个，选哪m-1个？这个也是贪心，要选r最小的m-1个，因为r大的尽量留给后面去操作。现在就是找va[x].fi<=va[i].se，并且va[x].se最小的m-1个。如果硬找，这可就不好实现了。
7.思考了一下，我发现，不用去找，而是开盒子。比如枚举到i的时候，这个点是否可以被前面的某个盒子给包括掉，首先当前的va[i].fi<=盒子所在的点。如果有多个的话，尽量选最左边的，因为留下右边的盒子给更右边的包裹。盒子可以都放在set里，找的时候lower_bound就可以。如果没找到，那么这个点开一个盒子，容量为m-1，因为自己要占用一个。如果找到了，那么这个盒子的容量-1，如果为0了，就把这个盒子删掉。当然有可能好几个盒子的位置一样，那么这个容量就累加就行了，如果盒子位置一样，就看成一个大盒子就了。
8.对于按左端点排序，从前往后遍历，枚举到第i个的时候，这个点如果被前面的包含了那就包含了，如果没有，那么这个点也不一定选，因为他还可能被后面的包含，所以就没法贪心了。如果按右端点，那么枚举到i的时候，如果他没被前面的包含，那么这个点是必拿的了，所以可以去贪心。当前按左端点排序后，倒序枚举可以，同理。

代码：

#include
#define int long long
#define PII pair<int,int >
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const int N = 2e5+5;

int T,n,m;
PII va[N];

map<int,int > mp;
set<int > s;

bool cmp(PII A,PII B)
{
	return A.se<B.se;
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
		if(m==1) //特判一下,省的下面再特判了
		{
			cout<<n<<"\n";
			continue;
		}
		sort(va+1,va+1+n,cmp);
		int ans = 0;
		mp.clear();s.clear();
		for(int i=1;i<=n;i++)
		{
			auto idx = s.lower_bound(va[i].fi);
			if(idx==s.end())
			{
				ans++;
				mp[va[i].se] += (m-1); //这个点盒子的容量+=m-1
				s.insert(va[i].se);
			}
			else
			{
				int now = *idx;
				if(--mp[now]==0) s.erase(now); //这个位置的盒子空了
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

CFdiv2-Permutation Restoration

题意：
就是给你一个b数组，然后让你求出来一个a数组，a数组是个全排列，对于b[i] = i/a[i]。让你把a数组构造出来。

思考：
1.首先b[i]和i都是已知的，看看每个b[i]对应a[i]的范围是多少，那么有，b[i]*a[i] <= i < (b[i]+1)*a[i]。那么i/(b[i]+1) < a[i] <= i/b[i]。所以每个b[i]需要的值的区间确定了。现在就是把这个全排列分给b，怎么分呢？
2.首先可以想到，从1到n，分别把这个i数字分给谁，但是想了想又不好分。
3.那么就只能枚举b，但是这个分配顺序，如何看呢？如果按左端点排序，每次枚举当前这个b，找出一个第一个>=左端点的数，分给他。感觉这样可以，实际上不行。因为你每次拿的是最小的数，那么剩下的就是越来越大的数，如果有一个个区间的右端点很小的怎么办？如图：

第一个值你分给大区间了，第二个值，小区间覆盖不了，所以就错了。
4.既然你想每次拿最小的分给b，那么剩下的数就会越来越大。那么就可以按右端点排序呀，这样右端点也是越拉越大，剩下的数也是越来越大，这就是最贪心。
5.你可能会问，那如果这个数给了第一个区间，会不会第二个数满足不了第二个区间？不会，如果第二个数满足不了第二个区间，有两种情况，一种是l太大，一种是r太小。如果l太大，第二个数都不够，那么第一个数更不够。如果r太小，第二个数连这个区间的r都大，肯定比第一个区间的r也大，更用不了。所以不会有这种情况。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 5e5+10,M = 2010;

struct node{
	int l,r;
	int id;
	bool operator<(const node &A)const{
		if(A.r!=r) return A.r<r;
		return A.l<l;
	}
};

int T,n,m,k;
int va[N];
int anw[N];
int l[N],r[N];

set<int > s;
priority_queue<node> q,qt;

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>n;
		s.clear();q = qt;
		for(int i=1;i<=n;i++) cin>>va[i];
		for(int i=1;i<=n;i++) s.insert(i);
		for(int i=1;i<=n;i++)
		{
			if(va[i]) l[i] = i/(va[i]+1)+1,r[i] = i/va[i];
			else l[i] = i+1,r[i] = n;
			q.push({l[i],r[i],i});
		}
		while(s.size())
		{
			auto t = q.top();q.pop();
			int tl = t.l,tr = t.r,id = t.id;
			auto can = *s.lower_bound(tl);
			s.erase(can);
			anw[id] = can;
		}
		for(int i=1;i<=n;i++) cout<<anw[i]<<" ";
		cout<<"\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

总结：
多多总结，真分析不出来的时候，就l和r排序都试试。