Week3 作业

Week3 作业

A题：选数问题（DFS）
问题描述：
给定n个数，从里面挑选K个数，使得它们的总和为S。输入共有T组数据（T<=100），每组数据有两行，第一行为n,K,S，第二行为n个数。输出共几种总和为S的数的组合。

解题思路：
举例说明：
有三个位置等待放数 ，共有1，2，3，4，5，6，7，8，9，10，十个数字，例如在某次DFS中，2放在第一个位置，则第二个位置只能从3-10选择一个，又如第二个位置选择了5，则第三个位置只能从6-10选择一个。即为，当前位置选数，从前一个位置选择数字的下一个数字开始，不能回头。代码中的last记录这个数字位置。

代码实现：

#include<iostream>
using namespace std;
int n,k,s,ans;
int a[100];


void dfs(int t,int sum,int last)
{
	if(t==k)
	{
		if(sum==s) ans++;
	}
	else 
	{
		for(int i=last;i<n;i++)
			dfs(t+1,sum+a[i],i+1);
	}
}

int main()
{
	int nn;
	cin>>nn;
	while(nn--)
	{
		cin>>n>>k>>s;
		for(int i=0;i<n;i++)
			cin>>a[i];
		ans=0;
		dfs(0,0,0);
		cout<<ans<<endl;
		
	}
}

B题：区间选点（贪心）

问题描述：
数轴上有n个闭区间[a_i,b_i]。取尽量少的点，使得每个区间内都至少有一个点。输入N个整数(N<=100)，之后N行每行两个整数a,b (a,b<=100)。输出选择点的个数。

解题思路：
1.设置区间的结构体数据结构，左端点和右端点，左端点升序，右端点降序。
2.now记录在现有的点的情况下，区间伸展的最右距离，起初点的个数为0，now为-1 。
3. 循环执行以下过程，将now与下一个区间的左端点比较，若now大，now赋值迁移到下一个区间的右端点，若now小，选点个数加一，now赋值迁移到下一个区间的右端点，直到遍历完所有区间结束。

代码实现：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct qj
{
	int l;
	int r;
	qj(int _l,int _r)
	{
		l=_l;
		r=_r;
	}
	bool  operator< (const qj& q)
	{
		if(r!=q.r) return r <q.r;
		else return l>q.l;
	}
};
int main()
{
	int n;
	cin>>n;
	vector<qj> v;
	while(n--)
	{
		int a,b;
		cin>>a>>b;
		qj x = qj(a,b);
		v.push_back(x);
	}
	sort(v.begin(),v.end());
	int count = 0;
	int now = -1;
	for(int i=0;i<v.size();i++)
	{
		if(v[i].l>now)
		{
			now = v[i].r;
			count++;
		}
	}
	cout<<count<<endl;
}

C题：区间覆盖（贪心）
问题描述：
数轴上有n(1<=n<=25000)个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定线段[1,T] (1<=T<=1000000)。覆盖整点，即[1,2]+[3,4]可以覆盖[1,4]。不可能办到输出-1。输入第一行为n和T，之后N行每行一个闭区间。输出选择区间的数目，不可能办到输出-1。

解题思路：
1.设置区间的结构体数据结构，左端点，右端点，左端点升序排列，有了这样的升序序列，我们只需要遍历一次所有区间即可。
2.两个重要变量，maxlen和nowbegin。nowbegin是当前覆盖到的最远距离，选择一个下面的区间，该区间满足这样的条件：左端点小于nowbegin，且右端点最大。用maxlen记录这个最大距离，然后用maxlen更新nowbegin。
3.循环的停止条件：a.下一个区间左端点没有小于nowbegin的，表示覆盖失败。b.所有区间已被遍历完成，此时需要判断nowbegin是否已经大于目标区间右端点。

代码实现：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct qj
{
	int l;
	int r;
	bool operator <(const qj& p)
	{
		 return l<=p.l;
		
	}
	qj(int x,int y):l(x),r(y){};
	qj(){};
};


int main()
{
	int begin =1,end,n,count = 0;
	cin>>n>>end;
	qj *v = new qj [n];
	int nowbegin = begin;
	for(int i=0;i<n;i++)
	{	
		scanf("%d%d",&v[i].l,&v[i].r);
	}
	sort(v,v+n);
	int i=0;
	int maxlen = 1;
	while(nowbegin<=end)
	{	
		if(v[i].l>nowbegin) break;
		bool flag = false;
		for(;v[i].l<=nowbegin&&i<n;i++)
		{
			if(v[i].r>maxlen)
			{
				maxlen = v[i].r;
				flag = true;
			}
				
			
		}
		if(flag)
		{
			nowbegin = maxlen + 1;
			count ++;
		}
		if(i==n) break;
	
		
	}
	if(nowbegin>end) cout<<count<<endl;
	else cout<<-1<<endl;
	
	
}