第一篇文章

贪心

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

字符串完美度

1.约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。
约翰不在乎字母大小写。（也就是说字母F和f）的完美度相同。给定一个字符串，输出它的最大可能的完美度。例如：dad，你可以将26分配给d，25分配给a，这样整个字符串完美度为77。
分析： 由排序不等式，出现次数最多的字母显然应该给26。所以这个题目变成了统计每种字母出现的次数了，然后按照出现次数从大到小，依次分配从高到低的权值。这就是最朴素的贪心思想。
最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程
输入
输入一个字符串S(S的长度 <= 10000)，S中没有除字母外的其他字符。
输出
由你将1-26分配给不同的字母，使得字符串S的完美度最大，输出这个完美度。
输入示例
dad
输出示例
77

经过差不多1个小时我才写出来这个简单入门题，大体思路很明确，就是找字母出现的次数，根据次数给权值。

#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
bool compare(int a, int b)
{
	return a>b;   //升序排列，如果改为return a>b，则为降序

}
int main() {
	std::string str;
	std::cin >> str;
	std::vector<int> v(26,0);
	for (int i = 0; i< str.size();++i) {
		int tmp;
		if (str[i] >= static_cast<int>('a') && str[i] <= static_cast<int>('z')) {
			tmp = str[i] - 'a';
		}
		else
			tmp = str[i] - 'A';

		v[tmp]++;
	}
	std::sort(v.begin(),v.end(), compare);
	int sum = 0;
	for (int i = 0,weight=26; v[i] != 0; i++,weight--) {
		sum += weight*v[i];
	}
	std::cout << sum;
}

活动安排问题一

2.有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？

分析： 我们就是想提高教室地利用率，尽可能多地安排活动。
考虑容易想到的几种贪心策略：

（1） 开始最早的活动优先，目标是想尽早结束活动，让出教室。
然而， 这个显然不行，因为最早的活动可能很长，影响我们进行后面的活动。例如活动开始和结束时间分别为[0, 100), [1,2) ,[2, 3), [3, 4),[4,5]，安排［0，100)的这个活动之后，其他活动无法安排，可是最优解是安排除它外的4个活动。

（2） 短活动优先， 目标也是尽量空出教室。但是不难构造如下反例： [0,5) [5,10) [3, 7), 这里[3,7)最短，但如果我们安排了[3,7)，其它两个无法安排了。但是最优解显然是安排其它两个，而放弃[3,7)，可见这个贪心策略也是不行的。

（3） 最后我们选择貌似不很对的思路，按完成的时间早晚排序。
每次选择离左边最近的活动开始，不断循环往复，最终求解。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
struct point{
    int start;
    int end;
};
point a[10000 + 10];
bool cmp(const point a,const point b){
    return a.end <= b.end;
}
int main(){
  //freopen("input.txt", "r", stdin); 
    int m,n;
    cin >> m;
    while(m--){
        cin >> n;
        for (int i = 0; i < n;i++){
            cin >> a[i].start >> a[i].end;
        }
        sort(a, a + n, cmp);
        int count = 1;
        int end=a[0].end;    
        for(int i=1;i<n;i++)    
            if(a[i].start>end){    
                end=a[i].end;    
                count++;    
            }    
        cout << count<<endl;
    }
}

活动安排问题二

有若干个活动，第i个开始时间和结束时间是[Si,fi)，活动之间不能交叠，要把活动都安排完，至少需要几个教室？

分析：能否按照之一问题的解法，每个教室安排尽可能多的活动，即按结束时间排序，再贪心选择不冲突的活动，安排一个教室之后，剩余的活动再分配一个教室，继续贪心选择……
反例： A：[1,2) B：[1,4) C：[5,6) D：[3，7)
已经按结束时间排好顺序，我们会选择
教室1： A C
教室2: B
教室3: D
需要3个教室。
但是如果换一种安排方法，我们可以安排AD在一个教室，而BC在另外一个教室，两个教室就够了。
所以之前的贪心策略解决不了这个问题。
所以要换种思路，我们可以按开始时间排序，每出现一个活动，若不能添加到当前教室，则增加一个教室。
如何证明此思路的正确性呢？假设当前有K个教室，对新出现的活动进行添加一个教室，说明此时k个活动都在进行，加上新出现的活动，刚好K+1个活动，已达到最优。
以下为具体实现，其中用到了优先级队列，优先级队列是以二叉堆为基础的数据结构。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;
const int maxn = 10000 + 10;

struct point{
    int start;
    int end;
};
point a[maxn];
bool cmp(point a,point b){
    if(a.start==b.start)
        return a.end < b.end;
    return a.start < b.start;
}
priority_queue<int, vector<int>, greater<int>> q;//优先级队列，按照从小到大排列
int main(){
    freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n;i++){
        cin >> a[i].start>>a[i].end;
    }
    sort(a, a + n, cmp);
    q.push(a[0].end);
    int count = 1;
    for (int i = 1; i < n;i++){
        if(a[i].start<q.top()){
            count++;
            q.push(a[i].end);
        }
        else{
            q.pop();
            q.push(a[i].end);
        }
    }
    cout << count << endl;
}