Week3 作业
A - 选数问题
题目：
从n个数中选出K个，使其之和等于S。问有多少种选法。
样例输入输出：
Input
1
10 3 10
1 2 3 4 5 6 7 8 9 10
Output
4
解析：
很简单的DFS问题。通过递归的方式实现深度优先搜索，通过剪枝进行优化。
代码：
#include <iostream>
using namespace std;
int a[16];
int n, k, s, ans = 0;
// N：数据个数 sum：和 step：加的数在数据中的位置
int dfs(int N, int sum, int step){
if(sum == s && N == k) {ans++; return 0;}
// 可行性剪枝
if(sum > s || N > k) return 0;
// 递归, 按次序step加数
for(int i = step ; i < n ; i++)
dfs(N + 1 , sum + a[i], i + 1);
}
int main(){
int T;
cin >> T;
for(int i = 0 ; i < T ; i++)
{
ans = 0;
cin >> n >> k >> s;
for(int j = 0 ; j < n ; j++)
cin >> a[j];
dfs(0, 0, 0);
cout << ans << endl;
}
}
B – 区间选点
题目：
数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。求最少的点数。
样例输入输出：
Input
3
1 3
2 5
4 6
Output
2
解析：
采用贪心策略。贪心的策略是：让我们选择的点出现在一个没有点的区间上，尽可能覆盖多的区间的地方。我们把所有的区间按照右边界升序排序。在第一个区间上找点时，为了让我们找的点能覆盖尽可能多的区间，我们选择最右面的点。之后我们遍历后面的区间，找到没有点的区间，选择最右面的点。解决我们的问题。
代码：
#include<iostream>
using namespace std;
int ans = 0;
// 区间结构体，左右边界
struct Interval{
int left;
int right;
}interval[105];
int main()
{
int n;
while(cin >> n)
{
for(int i = 0 ; i < n ; i++)
cin >> interval[i].left >> interval[i].right;
// 将区间按右边界升序排序
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n - 1 ; j++)
{
if(interval[j].right > interval[j + 1].right)
{
Interval tmp;
tmp = interval[j];
interval[j] = interval[j + 1];
interval[j + 1] = tmp;
}
}
int tag = 0;
tag--;
// 贪婪，向右使尽选点可能多的经过别的区间
for(int i = 0 ; i < n ; i++)
{
if(interval[i].left > tag)
{
tag = interval[i].right;
ans++;
}
}
cout << ans << endl;
}
}
回顾：
这道题相对较简单，而且数据体量较小，虽然我的代码AC了，但是写完后面C题（因为冒泡超时了）会发现上面的代码采用自己写冒泡排序是一个不明智的选择，以后要记得直接使用sort函数。
C – 区间覆盖
题目：
数轴上有 n (1<=n<=25000)个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t]（ 1<=t<=1,000,000）。输出最少的区间数，不可能办到输出-1。
注：覆盖整点，即(1,2)+(3,4)可以覆盖(1,4)。
样例输入输出：
Input
3 10
1 7
3 6
6 10
Output
2
解析：
与上面B题类似，这次的贪心的策略是在能连接区间左边的情况下找到向右扩展最长的位置。将区间按照左端点升序排序（左端点相同的按右端点降序，当然这个其实不排也行），从第一个区间开始，我们记下右端点的位置，向右扫描区间，直到左端点为刚刚记录的右端点的位置+1时，选择右端点最大的区间。如果不能连续，则区间不能被完全覆盖，输出-1。
代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int ans = 1;
// 区间结构体，左右边界
struct Interval{
int left;
int right;
}interval[1000000];
bool cmp(Interval a, Interval b)
{
return a.left < b.left;
}
int main()
{
int n, t;
cin >> n >> t;
for(int i = 0 ; i < n ; i++)
scanf("%d %d", &interval[i].left, &interval[i].right);
// 将区间按左边界升序排序，相同则按右边界升序
sort(interval, interval + n, cmp);
if(interval[0].left > 1)
{
printf("-1\n");
return 0;
}
int l = 1, tag = 1;
for(int i = 0 ; i < n ; i++)
{
if(interval[i].left <= l)
{
if(interval[i].right > tag)
tag = interval[i].right;
if(tag >= t) break;
}
else
{
l = tag + 1;
ans++;
if(interval[i].left <= l)
{
if(interval[i].right > tag)
tag = interval[i].right;
}
else
{
printf("-1\n");
return 0;
}
if(tag >= t)
break;
}
}
if(tag >= t)
printf("%d\n", ans);
else
printf("-1\n");
}
回顾：
刚开始手写冒泡复杂度n2超时了，而STL里的函数sort复杂度为nlogn要更优。以后尽量使用sort（之后课上学长也提到这一点了）。