4.钱币找零

/*
#include
#include
#include
using namespace std;
struct cmp
{bool operator()(vectorarry1, vectorarry2){return arry1[0] > arry2[0];}
};
int MaxNum(vector>& MoneyCut, int& money)
{//贪心策略：每一次都是使用最大面值的进行。int count = 0;//根据面值进行递减排序sort(MoneyCut.begin(), MoneyCut.end(), cmp());for (auto arr : MoneyCut){//0表示面值 1表示个数int c = money / arr[0];c = min(c, arr[1]);money -= c * arr[0];count += c;if (money == 0)return count;}if (money != 0)return -1;return count;
}
int main()
{vector < vector> moneycut = { {1,3},{2,1},{5,4},{10,3},{20,0},{50,1},{100,10} };int money = 0;cin >> money;cout << MaxNum(moneycut, money);
}
*/
#include
#include
#include
using namespace std;struct cmp
{bool operator ()(pair& p1, pair& p2){return p1.first > p2.first;}
};
template
int MaxNum(vector>& MoneyCut, int money)
{int count = 0;sort(MoneyCut.begin(), MoneyCut.end(), cmp());for (auto arr : MoneyCut){K c = money / arr.first;c = min(arr.second, c);money -= c * arr.first;count += c;if (money == 0)return count;}if (money != 0)return -1;return count;
}
int main()
{vector> moneycut = { {1,3},{2,13},{5,4 }, {10,3}, {20,0}, {50,1},{100,10} };int money = 0;cin >> money;cout << MaxNum(moneycut, money);
}

5.活动选择

/*#include
#include
#include
using namespace std;
//贪心策略：每次选择结束时间最早的活动
struct cmp
{bool operator()(vector&v1, vector&v2){return v1[1]>& events)
{int num = 1;int i = 0;sort(events.begin(), events.end(), cmp());for (int j = 1; j < events.size(); j++){//按照截止时间的顺序if (events[j][0] >= events[i][1]){num++;i = j;}}return num;
}int main()
{vector> events = { {1,4},{3,5},{0,6},{5,7},{3,8},{3,8},{5,9},{6,10},{8,11},{8,12},{2,13},{12,14} };cout << getMaxNum(events);
}
*/
#include
#include
#include
using namespace std;
struct cmp
{bool operator()(pair& p1, pair& p2){return p1.second < p2.second;}
};
template
int getMaxNum(vector>& events)
{sort(events.begin(), events.end(), cmp());int num = 1;int i = 0;for (int j = 1; j < events.size(); j++){if (events[j].first >= events[i].second){num++;i = j;}}return num;
}
int main()
{vector> events = { {1,4},{3,5},{0,6},{5,7},{3,8},{5,9},{6,10},{8,11},{8,12},{2,13},{12,14} };cout << getMaxNum(events);
}

6.无重叠区间OJ链接

第一种方式：

struct cmp
{bool operator()(vector&v1,vector&v2){return v1[1]>& intervals) {int num=1;int i=0;sort(intervals.begin(),intervals.end(),cmp());for(int j=1;j=intervals[i][1]){num++;i=j;}}return intervals.size()-num;}
};

 第二种方式：

struct cmp
{bool operator()(vector&v1,vector&v2){return v1[1]>& intervals) {int num=0;int i=0;sort(intervals.begin(),intervals.end(),cmp());for(int j=1;j=intervals[i][1]){i=j;}else{if(intervals[j][1]