week3 作业
记录week3的作业三道题
选数问题 区间选点 区间覆盖
选数问题：
第一行输入T，第二行输入n、K、S，第三行为数据
给n个数 选出K个使其和为S，T为测试组数。
Input 1
10 3 10
1 2 3 4 5 6 7 8 9 10
Output
4
思路大概就是利用dfs枚举子集，但是复杂度过高,所以可以剪枝，将和超过S的、数量超过K的去掉，通过return剪掉即可
#include<bits/stdc++.h>
//#include <iostream>
using namespace std;
int T;
int n,k,sum;
int ans;
int a[105]={0};
bool vis[105]={false};
void dfs(int position,int nowk,int s){
if(nowk>k||s>sum)return;
if(nowk==k&&s==sum){
ans++;return;}
for(int i=position;i<n;i++){//遍历数组找满足条件的解 超过条件的直接剪枝 //从position开始未选择过
if(vis[i]==false){
vis[i]=true;
int ss=s+a[i];
dfs(i+1,nowk+1,ss);
vis[i]=false;
}
}
}
void reset(){
ans=0;
for(int i=0;i<105;i++){
a[i]=0;vis[i]=false;}
}
int main(){
cin>>T;
for(int i=0;i<T;i++)
{
reset();
cin>>n>>k>>sum;
for(int i=0;i<n;i++){
cin>>a[i];
}
dfs(0,0,0);
cout<<ans<<endl;;
}
return 0;
}
区间选点
数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）
Input 第一行1个整数N（N<=100） 第2~N+1行，每行两个整数a,b（a,b<=100）
Output 一个整数，代表选点的数目
Input
2
1 5
4 6
Output
1
思路就是利用贪心策略，每一次选点都选择最右边的点，首先按照右端点从小到大排序，第一步令一个点为右端点最小的那条边的右端点，然后遍历所有边、每一步判断该点是否在这条边范围内，如果是继续，否则就更新这个点。
#include<iostream>
#include<algorithm>
using namespace std;
struct ste
{
int s;
int e;
}a[105];
bool cmp(ste a,ste b){
if(a.e!=b.e)return a.e<b.e;
else return false;
}
int main()
{
int i,n,count;
while(cin>>n)
{
count=1;
for(i=0;i<n;i++)//输入
{
cin>>a[i].s;
cin>>a[i].e;
}
sort(a,a+n,cmp);//按b从小到大排序
int newend=a[0].e;
//cout<<a[0].a<<" "<<a[0].b<<" "; //第一个
for(i=1;i<n;i++)
{
if(newend<a[i].s)
{
count++;
newend=a[i].e;
//cout<<time[i].a<<" "<<time[i].b<<" ";
}
}
cout<<count<<endl;
}
return 0;
}
区间覆盖：
描述
数轴上有 n (1<=n<=25000)个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t]（ 1<=t<=1,000,000）。
覆盖整点，即(1,2)+(3,4)可以覆盖(1,4)。
不可能办到输出-1输入 第一行：N和T 第二行至N+1行: 每一行一个闭区间。 输出 选择的区间的数目，不可能办到输出-1
样例输入 3 10 1 7 3 6 6 10
样例输出 2
区间覆盖和区间选点问题类似，按 a 从小到大排序，区间 1 的起点不是 1无解；否则选择起点在 1的最长区间。选择区间 [ai, bi] 后的起点应设置为 bi，然后继续遍历边，找到一条其起点小于bi、并且终点离bi最远的边，令其终点为新起点，重复该过程，注意[1,2]和 [3,4]可以覆盖[1,4]（大坑……
#include<iostream>
#include<algorithm>
using namespace std;
struct ste
{
int a;
int b;
}cow[25005];
//ste cow1[25005];
bool cmp(ste a,ste b){
return a.a<b.a;
//else return a.a>b.a;。。。
}
int main()
{
int n,s,t,sum;int _count=0;
while(scanf("%d%d",&n,&t)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d%d",&cow[i].a,&cow[i].b);
sort(cow,cow+n,cmp);
if(cow[0].a!=1){sum=-1;
cout<<"-1"<<endl;
continue;
}
s=cow[0].b;
int i =0;sum=1;
//for(int j=0;j<n;j++)cout<<cow[j].a<<" "<<cow[j].b<<" "<<_count<<endl;
int mark=0;
while(t-s>0){//直到覆盖完毕
//cout<<"cvrvre"<<endl;
int mostl=0;
for(i;i<n;i++)
{
if(cow[i].a<=s+1)
{
int temp=cow[i].b-s;
if(mostl<temp){
mostl=temp;
mark=i;
}
}
else break;
}
if(mostl==0)
{
sum=-1;break;
}
else{
sum++;
s=cow[mark].b;
}
}
cout<<sum<<endl;
}
return 0;
}