最小跳数
题目
给定一个非负整数数组，初始情况位于数组的第一个索引处。数组中的每个元素表示该位置的最大跳跃长度。要求达到最后一个索引花费的最小跳跃次数。
输入
2 3 1 1 4
输出
2
思路
如果不能一次走到，有以下操作：
- 假设从当前位置的
后一个候选点 出发，就是最优解
- 记录这个最优解位置为bestPointLoc，记录最优解的能跳数为theMax
- 遍历当前位置所有候选点，如果有候选点能走得更远，更新
bestPointLoc和theMax
原则：
- 原则0：从当前点出发，优先选择
候选点中能跳数更大的点
- 如输入3 5 1 1 4 6……，从3出发，优先选择跳到5
- 原则1：尽量走更远
- 需要同时满足上面两个原则
具体过程：
- 假设某个
候选点位置为i，对应的能跳数为arr[i]
- 如果arr[i]+i>=theMax+bestPointLoc，说明从
bestPointLoc点出发不比从位置为i的候选点出发走得远，所以需要更新bestPointLoc和theMax
- 或者arr[i]+i-bestPointLoc>=theMax，i-bestPointLoc是
候选点到最优解点距离，表示位置为i的点离当前点更远(比bestPointLoc离当前点远），尽管arr[i]本身可能没theMax大，但满足原则1
代码
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>
using namespace std;
int main(){
int length=0;
int arr[1001]={0};
while(cin>>arr[length++]){
if(cin.get()=='\n') break;
}
if(length==1){
cout<<0<<endl;
}else{
int i=0;
int res=0;
while(i<length-1){
int steps=arr[i];
if(steps>=length-1-i){
res++;
break;
}
int the_max=arr[i+1];
int bestPointLoc=i+1;
for(int j=i+2;j<=i+steps&&j<length-1;j++){
if(arr[j]+j-bestPointLoc>=the_max){
the_max=arr[j];
bestPointLoc=j;
}
}
res++;
i=bestPointLoc;
}
cout<<res<<endl;
}
}
|
举例
如输入3 1 1 2 4 1 1 1 1
- 先从3出发，设置the_max=1，能走到
1 1 2这三个点，前面两个1 1 能跳数一样，但因为第二个1比第一个1多走1个格子，所以优先选择第二个1，并保存到the_max=1(这个1是第二个1的能跳数)。但又发现可以走到2，并且2的 能跳数2+比第二个1再多走1个格子 大于the_max=1，所以先走到2
- 再从2出发，设置the_max=4，能走到4 1这两个点，如果走到1，虽然比4多走1格子，并且能跳数为1；但 能跳数1+多走的1格子 还是小于 能跳数4，所以走到4
- 再从4可以直接到终点
区间覆盖
题目描述
给出n个区间的起点和终点，求最少使用其中多少个区间可以将所有区间所在的区域完全覆盖。（测试的数据确保这1点）。
输入要求
第1行一个整数n，表示n个区间；
第2行开始n行，每行2个整数，表示一个区间范围。
类似[1,4][5,6]被认为是覆盖了[1,6]。
输出要求
从起点开始，按区间先后顺序，输出选中的区间。所选的区间应尽可能向终点扩展。
输入样例
7
1 5
1 6
3 6
1 7
6 9
9 10
7 9
输出样例
1 7
6 9
9 10
思路
1.将每一个区间按照左端点递增顺序排列，排完序后为[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]
2.设置两个变量 max_rightBorder和 leftPivot
max_rightBorder表示当前已经覆盖到的区域的最右边距离 .
leftPivot表示在剩下的线段中找到的所有左端点小于等于当前已经覆盖到的区域的右端点(leftPivot)的线段中，不断更新 最右边的距离
3.重复以上过程 直到区间全部覆盖 否则 区间不能全部覆盖
过程举例
假设第一步加入[1,4] ，那么下一步能够选择的有[2,6]，[3,5]，[3,6]，[3,7]（这四个左边界都小于4），由于7最大
所以下一步选择[3,7]，最后一步只能选择[6,8]，这个时候刚好达到了8退出，所选区间为3
代码
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;
struct Area
{
int left, right;
}area[100],r[100];
bool cmp(Area a,Area b){
if (a.left < b.left)
return true;
else if (a.left == b.left && a.right < b.right)
return true;
else return false;
}
int main() {
int n,i,cnt=0;
cin >> n;
for ( i = 0; i < n; i++) {
cin >> area[i].left >> area[i].right;
}
sort(area, area + n, cmp);
int leftPivot = area[0].left - 1;
int end = area[n - 1].right;
for (i = 0; i < n-1;) {
int max_rightBorder = area[i].right;
int max_interval = i;
while (area[i].left <= leftPivot + 1 && i < n) {
if (area[i].right > max_rightBorder) {
max_rightBorder= area[i].right;
max_interval = i;
}
i++;
}
leftPivot = max_rightBorder;
r[cnt++] = area[max_interval];
i = max_interval;
if (leftPivot == end)
break;
}
for (i = 0; i < cnt; i++){
cout << r[i].left << " " << r[i].right << endl;
}
return 0;
}
|
https://www.programminghunter.com/article/744488431/
https://blog.csdn.net/weixin_40852935/article/details/109687669
区间种树
题目
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1…n。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b<=e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t<=e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。
输入
共n+1行
第1行：输入一个n，表示有n户居民提出要求要在门前种树（1≤n≤100）
后n行：每行输入3个数bi、ei和ti，用空格隔开，分别表示第i户居民想在门前的起点bi到终点ei(包括端点)，想种ti颗树（1≤bi≤ei≤100）
输出
满足n户居民的最少种树量
样例输入
样例输出
提示
贪心（区间问题）
解题思路
首先题目要求是居民想种的树的各自区域可以相交，并且请你求出能够满足所有居民的要求,需要种树的最少数量，所以就可以想到尽量在相交的部分种树可以使种树的数量最少。
由于每位居民与上一位居民的相交处位于上一位居民的尾部，所以我们可以考虑从尾部开始种树。
排序的过程是先按照每户居民的结束位置从小到大排列，如果结束位置相等，则按照开始位置从大到小排列。
代码
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
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<iostream>
#include<algorithm>
using namespace std;
struct home
{
int b,e,t;
}dwelling[105];
int flag[10005]={0},sum;
void growTree(int e,int t)
{
while(t--)
{
flag[e--]=1;
}
}
int countTree(int b,int e)
{
sum=0;
for(int i=b;i<=e;i++)
if(flag[i])
sum++;
return sum;
}
int cmp(home x,home y)
{
if(x.e<y.e) return 1;
else if(x.e==y.e&&x.b>y.b) return 1;
else return 0;
}
int main()
{
int n,i,tot=0,tmp;
cin>>n;
for(i=1;i<=n;i++)
cin>>dwelling[i].b>>dwelling[i].e>>dwelling[i].t;
sort(dwelling+1,dwelling+1+n,cmp);
growTree(dwelling[1].e,dwelling[1].t);
tot+=dwelling[1].t;
for(i=2;i<=n;i++)
{
if(dwelling[i].b<=dwelling[i-1].e)
{
intersectNum=countTree(dwelling[i].b,dwelling[i-1].e);
if(intersectNum>=dwelling[i].t)
continue;
else{
growTree(dwelling[i].e,dwelling[i].t-intersectNum);
tot+=dwelling[i].t-intersectNum;
}
}
else
{
growTree(dwelling[i].e,dwelling[i].t);
tot+=dwelling[i].t;
}
}
cout<<tot;
return 0;
}
|
删除数字
题目
在给定的n个数字的数字串m中，删除其中k(k< n)个数字后，剩下的数字按原次序组成一个新的整数。请确定删除方案，使得剩下的数字组成的新整数最小。(1<=k<n<=240)
输入要求
输入有一行，先输入数字串m，再输入k，如描述所示。
保证数字串m没有前导0。
输出要求
输出有两行，第一行按顺序输出从左到右删除的k个数字，用空格隔开。（第一行里的输出顺序是按照被删除数字在原数中的顺序排列的，而不是按照删除的顺序排列的）
第二行输出删除k个数字后剩下的数字组成的新数，并换行。
输入
178543 4 16743 2 14832 1
输出样例
删除：7 8 5 4 留下：13
删除：6 7 留下：143
删除：8 留下：1432
思路
- 从前向后遍历，如果当前字符大于下一个，当前字符要被删除。
- 如 1
75482，删除4个。第一遍历，删除7；第二遍历，删除5；第三遍历，删除8 ；剩下：1 4 2，第四遍历，删除4，最终剩下：1 2
- 如果前面字符都没被删除，说明最后一个字符是最大的，删除最后一个字符
- 如 123456，删除4个。第一遍历，删除6，第二遍历，删除5……
代码
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
| #include<bits/stdc++.h>
using namespace std;
string res;
string str;
void foo(string str,int k){
int flag=1;
int end=str.length();
int length2=end;
int k2=k;
string str2=str;
while(k>0){
for(int i=0;i<end-1;i++){
if(str[i]>str[i+1]){
str.replace(i,1,"");
flag=0;
break;
}
}
if(flag){
str.replace(end-1,1,"");
end-=1;
}
k--;
}
int p1=0,p2=0;
string del="";
while(p1<=length2-k2) {
if(str[p1]==str2[p2]) {
p1++;
p2++;
}else {
if(del=="")
del+=str2[p2];
else
del=del+" "+str2[p2];
p2++;
}
}
cout<<"deleted ";
cout<<del<<endl;
cout<<"reserve ";
cout<<str<<endl;
}
int main(){
int k;
while(cin>>str>>k){
int length=str.length();
foo(str,k);
}
}
|
智力比赛游戏
题目
首先，比赛时间分为n个时段(n≤500),它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意:比赛绝对不会让参赛者赔钱！
输入要求
输入文共4行。
第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
输出要求
输出仅1行，表示小伟能赢取最多的钱
输入样例：
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出样例：
9950
思路
代码
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>
using namespace std;
struct node
{
int time,penalty;
};
bool cmp(struct node a, struct node b)
{
return a.penalty > b.penalty;
}
struct node arr[10000];
int t[10000] = {0};
int main()
{
int rewards,n;
cin>>rewards>>n;
int penalty_sum = 0;
for (int i = 0; i < n; i++)
cin >> arr[i].time;
for (int i = 0; i < n; i++)
{
cin >> arr[i].penalty;
penalty_sum += arr[i].penalty;
}
sort(arr, arr + n, cmp);
for (int i = 0; i < n; i++)
{
for (int j = arr[i].time; j >= 1; j--)
{
if (t[j] == 0){
penalty_sum -= arr[i].penalty;
t[j] = 1;
break;
}
}
}
cout << rewards - penalty_sum << endl;
}
|
