51nod确实是一个好oj，题目质量不错，wa了还放数据，学习算法来说挺好的，这次我做了几个水的贪心，虽然水，但是确实都很典型。
教程链接：http://www.51nod.com/tutorial/list.html
完美字符串
约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。
约翰不在乎字母大小写。（也就是说字母F和f）的完美度相同。给定一个字符串，输出它的最大可能的完美度。例如：dad，你可以将26分配给d，25分配给a，这样整个字符串完美度为77。
分析： 由排序不等式，出现次数最多的字母显然应该给26。所以这个题目变成了统计每种字母出现的次数了，然后按照出现次数从大到小，依次分配从高到低的权值。这就是最朴素的贪心思想。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cctype>
#include<cstdlib>
using namespace std;
const int maxn=;
int a[maxn];
string s;
bool cmp(const int a,const int b)
{
return a>b;
}
int main()
{
while(cin>>s)
{
memset(a,,sizeof(a));
for(int i=;i<s.length();i++)
a[tolower(s[i])-'a']++;
sort(a,a+,cmp);
long long sum=;
int b=;
for(int i=;i<;i++)
{
sum+=a[i]*b;
--b;
}
cout<<sum<<endl;
}
return ;
}
活动安排问题
有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？
分析：看似最不对的策略——结束时间越早的活动优先，才是正确的贪心。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=+;
typedef struct
{
int start;
int over;
}point;
point p[maxn];
const int cmp(const point a, const point b)
{
return a.over<=b.over;
}
int main()
{
int n;
while(cin>>n)
{
memset(p,,sizeof(p));
for(int i=;i<n;i++)
cin>>p[i].start>>p[i].over;
sort(p,p+n,cmp);
int cnt=;
for(int i=;i<n;i++)
{
for(int j=i+;j<n;j++)
{
if(p[i].over<=p[j].start)
{
i=j;
cnt++;
continue;
}
}
}
cout<<cnt<<endl;
}
return ;
}
活动安排问题二
有若干个活动，第i个开始时间和结束时间是[Si,fi)，活动之间不能交叠，要把活动都安排完，至少需要几个教室？
上一题的升级版
分析：如果只需要教室的个数，我们可以把所有开始时间和结束时间排序，遇到开始时间就把厚度加1，遇到结束时间就把厚度减1，显然最初始和最后结束时的厚度是0，在一系列厚度变化的过程中，峰值（最大值）就是最多同时进行的活动数，也是我们至少需要的教室数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=+;
int te[maxn],ts[maxn];
int main()
{
int n;
while(cin>>n)
{
for(int i=;i<n;i++)
scanf("%d%d",&ts[i],&te[i]);
sort(ts,ts+n);
sort(te,te+n);
int cnt=;
int mx=,j=;
for(int i=;i<n;i++)
{
if(ts[i]<te[j])
{
cnt++;
if(cnt>mx)
mx=cnt;
}
else if(ts[i]>te[j])
{
//cnt--;
j++;
}
else
{
j++;
}
}
cout<<mx<<endl;
}
return ;
}
独木舟问题
n个人，已知每个人体重，独木舟承重固定，每只独木舟最多坐两个人，可以坐一个人或者两个人。显然要求总重量不超过独木舟承重，假设每个人体重也不超过独木舟承重，问最少需要几只独木舟？
分析：按照人的体重排序，最轻的人跟最重的人尽量安排在一条船上，如果超过就安排最重的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<string>
#include<cctype>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=;
int a[maxn];
bool cmp(long long a,long long b)
{
return a>b;
}
int main()
{
int n;
long long m;
while(cin>>n)
{
scanf("%lld",&m);
long long x;
for(int i=;i<n;i++)
scanf("%lld",&a[i]);
sort(a,a+n,cmp);
long long cnt=;
int i=;
while(i<n)
{
if(a[n-]+a[i]<=m)
{
cnt++;
n--;
i++;
}
else
{
i++;
cnt++;
}
//cout<<a[i]<<"jk"<<a[n-1-i]<<endl;
}
//cout<<i<<"io"<<endl;
cout<<cnt<<endl;
}
return ;
}
任务执行顺序
有N个任务需要执行，第i个任务计算时占R[i]个空间，而后会释放一部分，最后储存计算结果需要占据O[i]个空间（O[i] < R[i]）。
分析：
可以抽象成，从一个整数开始，每次减去a，再加上b (a,b都是正数)，要求每次操作都不产生负数。
令a[i] = R[i], b[i] = R[i] – O[i]，O[i] < R[i],有0<b[i]<a[i]。 所以尽管每次有减有加，但是加的没有减的多，总数在不断减小。所以——按照b[i]不增的顺序排序，是最“有利”的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
long long r[maxn],o[maxn],b[maxn],a[maxn];
bool cmp(long long a,long long b)
{
return a>b;
}
int main()
{
int n;
while(cin>>n)
{
for(int i=;i<n;i++)
scanf("%lld%lld",&r[i],&o[i]);
for(int i=;i<n;i++)
{
a[i]=r[i];
b[i]=r[i]-o[i];
}
sort(b,b+n,cmp);
long long mx=0x3fff;
long long ans=;
for(int i=;i<n;i++)
{
ans-=a[i];
if(ans<mx)
mx=ans;
ans+=b[i];
}
cout<<(-mx)<<endl;
}
return ;
}