贪心

贪心：每一步行动总是按某种指标选取最优的操作来进行， 该指标只看眼前，并不考虑以后可能造成的影响。

局部最优 → 整体最优。

区间问题

区间选点

给定 N 个闭区间 [ai,bi ]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 N，表示区间数。

接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

1≤N≤105,
−109≤ai≤bi≤109

此题同理：最大不相交区间数量

给定 NN 个闭区间 [ai,bi][ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

思路：

右端点排序，直接对比。下面是题解

左端点排序的话，逆序对比。

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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
pair<int,int> v[N];
bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.second<b.second;
}
int main(void)
{
    int n;scanf("%d",&n);
    for(int i=0;i<n;i++)
        cin>>v[i].first>>v[i].second;
        
    sort(v,v+n,cmp);
        
    int res = 0,ed = -2e9;
    for(int i=0;i<n;i++)
    {
        if(v[i].first>ed) {
            res++;
            ed = v[i].second;
        }
    }
    cout<<res;
}

区间合并

给定 N 个闭区间 [ai,bi][ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

输出最小组数。

输入格式

第一行包含整数 N，表示区间数。

接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式

输出一个整数，表示最小组数。

数据范围

1≤N≤105,
−109≤ai≤bi≤109

左端点排序：

1.逻辑解释：

当第cnt个区间的左端点小于前cnt - 1个区间的最小的max_r时，前cnt -1个区间的左端点不一定都小于第cnt个区间的左端点，因为是按照右端点排序的。如果有些区间的左端点大于第cnt个区间的左端点，并且大于另一些区间的max_r，就不能保证这cnt个区间都有一个共同点（就是第cnt个区间的左端点）。

2.反证解释：

按照右边排序的话，各个区间的左端点不能保证单调性，所以有可能第三个区间的左端点比第一个区间的左端点还要左边，它可以特别长。

反例： [1, 3], [2, 5], [4, 100], [10, 13]

3.比喻：

比如，有n个人需要用教室，每个人占用教室的起始时间和终止时间是不一样的。
1、如果想知道只有一间教室，能安排下的最多不冲突人数（不是所有的人都有机会，有的会被舍掉）是多少（区间选点和最大不相交问题），那么当然是最先结束的人排在前面，这样后面的人才有更多机会。如果是按左端点排序，那么如过一个人0点开始用，那么肯定他排在最前面，但是如果他自己就占用了24小时，那么只能给他一个人用了，这样就达不到最大的效果。所以按左端点排序。
2、如果想知道这些人都必须安排，没有人被舍弃，至少需要多少个教室能安排下（区间分组问题）。那么肯定是按照开始时间排序，开始时间越早越优先。这样每间教室都能得到最充分的利用。

偷偷说：实际按左右无所谓的。这题的区间只是一个一维坐标系，如果要按右端点排序，那你就从右往左找 min_r 好了。只是一个方向问题。

==思路：==

1.将所有区间按左端点从小到大排序

2.从前往后判断 ： if L[i] > Max_r ，即是否能将其放到某个现有的组中

​ ①如果存在，将其放进去，并更新当前组的 MAX_r

​ ②如果不存在，开新组，然后再将其放进去

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
#include <iostream>
#include <algorithm>
#include <queue>

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<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i ++ )
    {
        //小根堆里存的是每个分组的最大右端点，
        //当前要判断的区间的左端点至少要大于其中一个分组的最大右端点，才会用更新替代开新组。
        auto it = range[i];
        if (heap.empty() || heap.top() >= it.l) heap.push(it.r); //开新组
        else
        {
            heap.pop();         //不开组，更新当前组的MAX_r。
            heap.push(it.r);
        }
    }

    printf("%d\n", 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.从左到右按左端点排序

2.从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间，

然后将start更新成右端点最大值

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int st,ed;
int n;
typedef pair<int,int> PII;
PII range[N];


int main(void)
{
    scanf("%d%d",&st,&ed);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int a,b;cin>>a>>b;
        range[i] = {a,b};
    }
    sort(range,range+n);

    bool success = false;
    int res  = 0;

    for(int i=0;i<n;i++)
    {
        int j=i, r = -2e9;

        while(j<n && range[j].first<=st) //第一步：找最大右端点
        {
            if(range[j].second>r){
                 r = range[j].second;
            }
            //r = max(r,range[j].r);
            j++;
        }
        if(r<st){
            res = -1;
            break;
        }
        
        res++; //放在判断前
        
        if(r>=ed) {
            success = true;
            break;
        }
        st =r;   //第二步：更新左端点start
        i = j-1;
    }

    if(success){
        cout<<res;
    }
    else cout<<-1;

}

Q :最后为什么是i=j-1 而不是i=j ?

A :比如说： j扫描到了 2 此时while() 退出了 我们下次 i 应该从 2开始但是需要注意的是我们的for()循环 i++ ,i还会加1次 此时 我们的 i=3 直接从 3 开始循环了，故需要减1。

Q ：那为什么不把i++去掉，然后i = j好理解一点

A ：因为j不一定会++,这样可能会死循环

哈夫曼树（堆）

合并果子

在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

达达决定把所有的果子合成一堆。

每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过 n−1n−1 次合并之后，就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为 11，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

例如有 33 种果子，数目依次为 1，2，91，2，9。

可以先将 1、21、2 堆合并，新堆数目为 33，耗费体力为 33。

接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 1212，耗费体力为 1212。

所以达达总共耗费体力=3+12=15=3+12=15。

可以证明 15 为最小的体力耗费值。

输入格式

输入包括两行，第一行是一个整数 n，表示果子的种类数。

第二行包含 n 个整数，用空格分隔，第 i 个整数 ai 是第 i种果子的数目。

输出格式

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

输入数据保证这个值小于 231。

数据范围

1≤n≤10000,
1≤ai≤20000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<queue>
using namespace std ;
int res;
int main(void)
{
    priority_queue<int,vector<int>,greater<int> > heap;
    int n;cin>>n;
    while(n--) {
        int x ;
        scanf("%d",&x);
        heap.push(x);
    }
    
    while(heap.size()>1)
    {
        int a = heap.top();heap.pop();
        int b = heap.top();heap.pop();
        res += a+b;
        heap.push(a+b);
    }
    printf("%d",res);
    
}

排序不等式

排队打水

有 n 个人排队到 11 个水龙头处打水，第 ii 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

输入格式

第一行包含整数 n。

第二行包含 n 个整数，其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。

输出格式

输出一个整数，表示最小的等待时间之和。

数据范围

1≤n≤105,
1≤ti≤104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
long long res;
int main(void)
{
    int a[N],n;
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        res += a[i]*(n-1-i);
    }
    cout<<res;
}

绝对值不等式

货仓选址

在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 N。

第二行 N 个整数 A1∼AN。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

1≤N≤1000001≤N≤100000,
0≤Ai≤40000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std ;
const int N = 1e5+10;
int n;
int a[N];
int res;
int main(void)
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        res += abs(a[i]-a[n/2]);
    }
    cout<<res;
}


推出来的不等式

耍杂技的牛

农民约翰的 N 头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数 N，表示奶牛数量。

接下来 N 行，每行输入两个整数，表示牛的重量和强壮程度，第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。

输出格式

输出一个整数，表示最大风险值的最小可能值。

数据范围

1≤N≤50000,
1≤Wi≤10,000,
1≤Si≤1,000,000,000

既然是推出来的不等式，下面来贴下推理过程：

/ 交换前 交换后
第i头牛 W1+W2+…W(i-1) - Si W1+…Wi-1+Wi+1 - Si
第i+1头牛 W1+W2+…Wi - S(i+1) W1+…Wi-1 - S(i+1)

去掉重复的W1+….W(i-1) , 得

/ 交换前 交换后
第i头牛 - Si Wi+1 - Si
第i+1头牛 Wi - S(i+1) - S(i+1)

题目所求答案为危险系数最大值的最小值，所以找到最大值就OK。

对于上表，易知 Wi -S(i+1) > -S(i+1) , Wi+1-Si > -Si ；

故交换前取最大值 Wi -S(i+1) ,交换后去最大值 Wi+1-Si 。

假设交换后，我们得到的是最小值（这样假设得到的式子能够帮助我们求得答案），则有不等式：

Wi - S(i+1) > Wi+1 - Si ，即交换后变小。

移项得 Wi + Si > Wi+1 + Si+1 。

此时我们发现，设 Q = W+S ，只需要按照Q对输入排序(也就是完成交换的过程)，再依次比较。

取Q1 … Qi 中的最小值即可。

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
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
PII cow[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int s, w;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};
    }

    sort(cow, cow + n);

    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        int s = cow[i].first - cow[i].second, w = cow[i].second;
        res = max(res, sum - s);
        sum += w;
    }

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

    return 0;
}

以前的题

圣诞节来临了，圣诞老人准备分发糖果，现

在有多箱不同的糖果，每箱糖果有自己的价值和重

量，每箱糖果都可以拆分成任意散装组合带走。圣

诞老人的驯鹿雪橇最多只能装下重量W的糖果，请

问圣诞老人最多能带走多大价值的糖果。

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
#include<iostream>
#include<algorithm>
#include<memory.h>
#include<iomanip>
const  double eps = 1e-6;
using namespace std;
int W;
double V;
struct suger{
	int w;
	int v;
	bool operator<(const suger& s){
		return double(v)/w-double(s.v)/s.w>eps;
	}
}sugers[110];
void greedy(int &total,int &n){
	for(int i=0;i<n;i++){
		if(total+sugers[i].w<=W){
			total += sugers[i].w;
			V += sugers[i].v;
		}
		else {

			V += sugers[i].v* double(W-total)/sugers[i].w;			W = W+W-total;
	        break;
	    }
    }
}
int main(void)
{
    int n,total=0;
    cin>>n>>W;
    for(int i=0;i<n;i++){
		cin>>sugers[i].v>>sugers[i].w;
	}
	sort(sugers,sugers+n);//自己写
	
    greedy(total,n);
    cout<<fixed<<setprecision(1)<<V;

}

点击并拖拽以移动

各地放了多部电影 ，给定每部电影的放映时间区间，区间重叠的电影不可能同时

看（端点可以重合），问李雷最多可以看多少部电影。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int total;
struct film{
	int s;
	int e;
	bool operator<(const film& f){
		return e<f.e;
	} 
}f,films[110];
int main(void)
{   int n;cin>>n;
    for(int i=0;i<n;i++){
		cin>>films[i].s>>films[i].e;
	}
	sort(films,films+n);
	total++;f=films[0];
    for(int i=1;i<n;i++){
		if(f.e<=films[i].s){
			total++;
			f=films[i];
		}
	}
	cout << endl<<total;
}

点击并拖拽以移动

有 n头牛（1<=n<=50,000)要挤奶。给定每头牛挤奶的时间区

间[A,B] (1<=A<=B<=1,000,000，A,B为整数)。

牛需要呆畜栏里才能挤奶。一个畜栏同一时间只能容纳一头牛。

问至少需要多少个畜栏，才能完成全部挤奶工作，以及每头牛都

放哪个畜栏里（Special judged)

去同一个畜栏的两头牛，它们挤奶时间区间哪怕只在端点重合也

是不可以的。 

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
61
62
63
//难点：优先队列的运用 + 配合贪心和队列的排序
//（奶牛和栅栏的顺序定义operator，栅栏和奶牛都需要no来记录原顺序编号） 
#include<iostream>                     //（因为它们都被排序打乱了 ） 
#include<algorithm> //ps：循环均为从1开始
#include<queue>
using namespace std;
struct cow{
	int s;//时间区间 start -end 
	int e;
	int no; //奶牛编号：防止原奶牛顺序 由于进入时间的排序而被打乱 
	operator<(const cow& c){ //排序 
		return s<c.s;
	}
}cows[100];
int pos[100];
typedef struct fence{
	int e;//栅栏的结束时间不断在变 ，作为队列排序依据
	int no; //栅栏编号，方便记录奶牛进入的栅栏（同样是防止队列顺序更新而失去原顺序编号） 
	bool operator<(const fence & f) const {
	return e > f.e; 
	}
	fence(int e,int n):e(e),no(n){};// 对栅栏赋值。 
}fen;
int total; //栅栏数 
int main(void)
{  //1.奶牛赋值+排序 
    int n;cin>>n;
    for(int i=1;i<=n;i++){
		cin>>cows[i].s>>cows[i].e;
		cows[i].no=i;//排序前，在赋值no过程记录好原位置 
	}
    sort(cows+1,cows+n+1); 
    //2.栅栏赋值+排序 
    priority_queue<fen> pq;
    for(int i=1;i<=n;i++){	
		if(pq.empty()){//情况1.最开始（无奶牛） 
			++total;
			pq.push(fen(cows[i].e,total));
			pos[cows[i].no]=total;
		}
		else { //情况2. next奶牛与目前栅栏冲突 
			
			fen f=pq.top();//利用排序（目前结束最快） 找到待命栅栏 
			
			if(f.e>=cows[i].s){
			++total;
		    pq.push(fen(cows[i].e,total)); //冲突加入新栅栏，编号即total 
		    pos[cows[i].no]=total;
		    }
		    else {//情况3. 不冲突 
            //不冲突：total不变，队列弹出原奶牛，压入新奶牛 
				pq.pop();                 
		        pos[cows[i].no]=f.no;    //进入编号为top（待命）的栅栏 
				pq.push(fen(cows[i].e,f.no)); //不冲突使用原栅栏
			}
			
		}
	}
	//3.循环结束，事件结束,输出 
	cout<< total<<endl;
	for(int i=1;i<=n;i++)
	    cout<<pos[i]<<endl;
}

点击并拖拽以移动

放置雷达：

img点击并拖拽以移动

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
61
62
63
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int n,d,total;
class how{
	public:
		bool operator()(pair<double,double> p1,pair<double,double> p2){
			   return p1.first<p2.first;
		}
};
bool decide(vector<pair<double,double> > m,int F,int i)
{
	for(int k=F;k<i;k++){
		if(m[i].first<=m[k].second&&m[i].first>=m[k].first)
	        continue;
		else return false;
	}
	return true;
	
}
void dfs(const vector<pair<double,double> >&m)
{
	int FNC=0;
	while(1)
	{   
	    int i;
		for(i=FNC+1;i<n;i++)
		{  
			if(decide(m,FNC,i)) continue;
			else{
				FNC=i;
				total++;
				break;
			}
		} 
		if(i>=n) {
			total++;
			break;
		}
	}
	
}
int flag=1;
int main(void)
{   
	while(cin>>n>>d&&n!=0){
	total=0;
	vector<pair<double,double> > m;
	for(int i=0;i<n;i++){
		int x,y;cin>>x>>y;
    	pair<double,double> p;
		p.first =x-sqrt(d*d-y*y);
		p.second=x+sqrt(d*d-y*y);
		m.push_back(p);
	}
    sort(m.begin(),m.end(),how());
	dfs(m);
    cout<<"case"<<flag<<":"<<total<<endl;
    flag++;
    }
}

点击并拖拽以移动

快来参与讨论吧~