輸入輸出：
本題其實思路上比較簡單捧搞。要求我們從一組數(shù)中選擇一定個數(shù)的數(shù)使他們的和滿足一定的條件，我們可以暴力钓株，但思考下來暴力的時間耗費巨大实牡，所以我們應該思考其他算法。
首先既然是選擇數(shù)字使得和達到某一個條件轴合，首先應該把數(shù)字的大小排一下序创坞。然后定下一個左界和一個右屆，選數(shù)的話從小的往大的開始選（不再回頭選）受葛，超過該數(shù)或達到要求則直接返回再從之前選的地方跳過一個數(shù)字進行選题涨。（即這次選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;
}
上碼巡雨，題目不算太難
Input
2
1 5
4 6
Output
1
Input
3
1 3
2 5
4 6
Output
2
這個題就比較有意思，我們要找數(shù)量最小的點去做到每個區(qū)間內(nèi)都至少存在一個點席函。
為了達到數(shù)量最少和覆蓋全部兩個方面的條件铐望，我們可以給出一個選點策略。達成這兩方面要求茂附，
1.首先把全部的區(qū)間段按作一個排序正蛙，第一關(guān)鍵字右邊界，第二關(guān)鍵字左邊界营曼。
2.點的范圍向右擴展乒验，擴展到一個區(qū)域后判斷下一個區(qū)間的左界是不是在已經(jīng)擴展的范圍內(nèi)，不在就追加一個點蒂阱，右屆就擴展到該區(qū)間的右屆锻全。
這樣一來首先我們是遍歷區(qū)間擴展的，全部覆蓋肯定是能實現(xiàn)录煤，其次由于我們是根據(jù)兩個關(guān)鍵字排序鳄厌。不可能實現(xiàn)更少的點去全部覆蓋這些區(qū)間（所以選點的策略依然是貪心
了解了這個之后就開心寫碼
#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.區(qū)間覆蓋
乍一看這題就和上一個差不多的亞子。
不過這題要做的是覆蓋[1,t]
我們依然可以根據(jù)剛剛的思路辐赞。首先根據(jù)右屆為第一關(guān)鍵字部翘，左界為第二關(guān)鍵字作一個排序硝训。然后從左界1開始向右擴展响委。擴展的方式則是先從右屆最大的范圍內(nèi)遞減的找到，直到找到左界符合要求的（要是一個符合要求左界都找不到窖梁，那就是不存在）赘风。
找到一個之后最新的右邊框就變成了所選區(qū)間的右屆，當然這題讓我調(diào)了最久的還是……整點覆蓋問題（[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;
}
然后這是代碼（逃
