image.png
输入输出：
image.png
本题其实思路上比较简单。要求我们从一组数中选择一定个数的数使他们的和满足一定的条件，我们可以暴力，但思考下来暴力的时间耗费巨大，所以我们应该思考其他算法。
首先既然是选择数字使得和达到某一个条件，首先应该把数字的大小排一下序。然后定下一个左界和一个右届，选数的话从小的往大的开始选（不再回头选），超过该数或达到要求则直接返回再从之前选的地方跳过一个数字进行选。（即这次选1 2 3，下次换1 2 4）。
这样的话思路可以由递归完成。
#include<iostream>
#include<algorithm>
using namespace std;
int temp=0;
int a[1000000];
void choose(int a[],int sum,int lf,int rt,int k)
{
if(k==0&&sum==0)
{
temp++;
return;
}
for(int j=lf;j<rt;j++)
{
if(a[j]>sum)
{
break;
}
choose(a,sum-a[j],j+1,rt,k-1);
}
}
int main()
{
int n;
int k,s,l;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>l>>k>>s;
for(int j=0;j<l;j++)
{
cin>>a[j];
}
sort(a,a+l);
int sum=0;
choose(a,s,0,l,k);
cout<<temp<<endl;
}
return 0;
}
上码，题目不算太难
image.png
image.png
Input
2
1 5
4 6
Output
1
Input
3
1 3
2 5
4 6
Output
2
这个题就比较有意思，我们要找数量最小的点去做到每个区间内都至少存在一个点。
为了达到数量最少和覆盖全部两个方面的条件，我们可以给出一个选点策略。达成这两方面要求，
1.首先把全部的区间段按作一个排序，第一关键字右边界，第二关键字左边界。
2.点的范围向右扩展，扩展到一个区域后判断下一个区间的左界是不是在已经扩展的范围内，不在就追加一个点，右届就扩展到该区间的右届。
这样一来首先我们是遍历区间扩展的，全部覆盖肯定是能实现，其次由于我们是根据两个关键字排序。不可能实现更少的点去全部覆盖这些区间（所以选点的策略依然是贪心
了解了这个之后就开心写码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int max(int a, int b)
{
if (a > b)
return a;
else return b;
}
int min(int a, int b)
{
if (a < b)
return a;
else return b;
}
struct quyu
{
int lf;
int rt;
};
bool cmp(quyu x, quyu y)
{
if(x.rt == y.rt)
return x.lf > y.lf;
return x.rt < y.rt;
}
int main()
{
int m;
int now=0;
int temp = 0;
int size = 0;
quyu a[100000];
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> a[i].lf >> a[i].rt;
}
sort(a,a+m,cmp);
for(int i = 0; i < m; i++)
if(a[i].lf > now) {
now = a[i].rt;
temp++;
}
cout <<temp<<endl;
return 0;
}
3.区间覆盖
image.png
image.png
乍一看这题就和上一个差不多的亚子。
不过这题要做的是覆盖[1,t]
我们依然可以根据刚刚的思路。首先根据右届为第一关键字，左界为第二关键字作一个排序。然后从左界1开始向右扩展。扩展的方式则是先从右届最大的范围内递减的找到，直到找到左界符合要求的（要是一个符合要求左界都找不到，那就是不存在）。
找到一个之后最新的右边框就变成了所选区间的右届，当然这题让我调了最久的还是……整点覆盖问题（[1，2][3，4]能覆盖一到四QAQ）
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct quyu
{
int lf;
int rt;
};
bool cmp1(quyu x, quyu y)
{
if (x.rt == y.rt)
return x.lf > y.lf;
return x.rt < y.rt;
}
bool cmp2(quyu x, quyu y)
{
return (x.lf < y.lf);
}
int main()
{
int ok = 0;
int m, n;
int now = 0;
int qs = 1;
int temp = 1;
int size = 0;
// quyu a1[1000000];
quyu a2[100000];
cin >> m >> n;
temp = 1;
qs = 1;
int max;
now = 1;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &a2[i].lf, &a2[i].rt);
// cin >> a2[i].lf >> a2[i].rt;
}
for (int i = 1; i <= m; i++)
{
if (a2[i].lf <= 1 && a2[i].rt > now)
{
now = a2[i].rt;
}
}
if (now == 1)
{
cout << "-1" << endl;
}
else if (now >= n)
{
cout << "1" << endl;
}
else
{
sort(a2 + 1, a2 + m + 1, cmp1);
while (now < n)
{
ok = 0;
for (int i = m; i >= qs; i--)
{
// cout<<now<<endl;
if (a2[i].rt < now)
break;
//cout<<a2[i].rt<<endl;
if (a2[i].lf <= now + 1)
{
// cout<<i<<" "<<a2[i].lf<<" "<<a2[i].rt<<endl;
//1 2 3 4 5 6
//1 2 3 4 5 6
now = a2[i].rt;
qs = i + 1;
temp++;
ok = 1;
break;
}
}
if (!ok)
{
cout << "-1" << endl;
break;
}
}
if (ok)
{
cout << temp << endl;
}
}
return 0;
}
然后这是代码（逃
网友评论