贪心解题报告"/>
2018SCUACM Training 1 贪心解题报告
A - LiAlH4的字符串
题意：输入一个字符串s(s.length<=1e4) 包含26个字母（不分大小写）给每个字母分别分配（1~26）价值度，字母出现次数越多价值 度越高。输出总价值。
题解： 签到题，但是由于数组开小了（小了一位），第一次提交RE，后面两次都是TLE，不太清楚数组开小为什么会是TLE……所以以为是算法的问题，后来才发现是代码写丑了……
本题就是维护一个用来计数的map或数组，然后将字母按价值度排序（出现次数越多价值越高），然后计算总价值，因为本题只有26个字母，所以可以不用map，只用数组，未出现的字母次数置零即可。
AC代码：（数组）
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstdio>
using namespace std;
map<char,int>al;
int a[26];
char s[15000];
int main(){
// freopen("input(3).txt","r",stdin);scanf("%s",s);for (int i=0;i<strlen(s);i++){if (isupper(s[i])) s[i]=tolower(s[i]);a[s[i]-'a']++;}sort(a,a+26);
// for (int i=0;i<26;i++) cout<<a[i]<<endl;int sum=0;for (int i=25;i>=0&&a[i];i--)sum+=a[i]*(i+1);cout<<sum;
}AC代码：（map，不推荐）
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
map<char,int>al;
int main(){char s[10005];scanf("%s",s);int len=strlen(s);for (int i=0;i<len;i++)if (s[i]<'a') s[i] =s[i]+32;for (int i=0;i<len;i++){if (al.count(s[i])) al[s[i]]++;else al[s[i]]=1;}int i=0;map<char,int> ::iterator it;int a[26];for (it = al.begin();it!=al.end();it++)a[i++]=it->second;int sum=0;sort(a,a+i);
// for (int i=0;i<3;i++) cout<<a[i]<<endl;for (int j=i-1,t=26;j>=0;j--,t--)sum+=a[j]*t;cout<<sum;}B - Glory的字符串
题意：
输入一个只包含小写字母的字符串s，判断s是否能改写成含有“a”到“z”共26个小写字母的递增子序列，若能则将其改写后输出，改写标准是一个字母只能改写成比它大的字母，如a能写成b但b不能写成a。若不能则输出-1.
题解：
注意是子序列，可以不连续，刚开始没想到这一点，WA了两次。
输入字符串s后进行遍历，维护一个用来计数的计数器，若找到可以改写为a的字母则继续找b，同时改写s，计到26个字母时输出，
否则输出-1
AC代码：
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstdio>
using namespace std;
int len;
int find(char *c){int t=0;for (int i=0;i<len;i++){if (*(c+i)>('a'+t)) continue;*(c+i)='a'+t;t++;if (t==26) return 1;}return 0;
}
char al[]="abcdefghijklmnopqrstuvwxyz";
char s[100000+100];
int main(){scanf("%s",s);len=strlen(s);int ok;ok=find(s);if (!ok) cout<<-1;else cout<<s;} C - Sidney的烧烤
题意：给你M块钱到N家摊位买烧烤，第 i 家烧烤摊有 J[i] 串烧烤，总价为F[i] 元。问如何买才能使买到的烧烤最多，输出最多能买到的烧烤（保留三位小数），其中烧烤可以不买整串而只买一部分。
题解：一开始没想到要怎么处理输入和将烧烤按价值排序（单价越低优先度越高），后来想到照选择排序的方法给每个单价一个排名，遍历找排名最大的，由于写的时候又把代码写丑了（一个计数的变量j该重置为-1时重置为0），所以WA了好几次，（最开始又由于弄了个变长数组CE了）在输入的同时存入单价，然后排名，最后遍历加串数，钱不够时用钱除以单价把串数求出来
AC代码：（排名）
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstdio>
#include<utility>
using namespace std;
int J[1000+50]={0},F[1000+50]={0};
int r[1000+50]={0};
double s[1000+50]={0.0};
int main(){int M=0,N=0;while (scanf("%d%d",&M,&N)&&M!=-1&&N!=-1){for (int i=0;i<N;i++){scanf("%d%d",&J[i],&F[i]);s[i]=double(F[i])/J[i];}for (int i=1;i<N;i++)for (int j=0;j<i;j++)if (s[j]<=s[i]) r[i]++;else r[j]++;/*for (int i=0;i<N;i++)cout<<r[i]<<endl;*/double ans=0;int i=0;for (int j=0;j<N;j++){if (r[j]==i&&M>=F[j]) {ans+=J[j];M=M-F[j];i++;j=-1;}else if (r[j]==i&&M<F[j]) {ans=ans+M/s[j];break;}}printf("%0.3lf\n",ans); memset(J,0,sizeof(J));memset(F,0,sizeof(F));memset(r,0,sizeof(r));memset(s,0,sizeof(s));}
} 但这不是最优的，因为每次都要遍历一遍数组找排名，最优的是用结构自己写一个比较函数sort好然后依次计算，时间上快了一倍；
AC代码：（结构）
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 1010;struct node
{double num, sum;
}a[maxn];bool cmp(node &a, node &b)
{return a.num / a.sum > b.num / b.sum;
}int main()
{int n, m;while (scanf("%d%d", &n, &m) == 2 && n + m != -2){for (int i = 0; i < m; i++)scanf("%lf%lf", &a[i].num, &a[i].sum);sort(a, a + m, cmp);double ans = 0;for (int i = 0; i < m; i++){if (n > a[i].sum){ans += a[i].num;n -= a[i].sum;}else{ans = ans + a[i].num / a[i].sum*n;break;}}printf("%.3lf\n", ans);}return 0;
}另外，如果是用float也会WA，可能是因为后台给的测试数据是double吧
附上double（有效16位）和float（有效7位）的区别：
D - NaOH的讲座
题意：分别输入n（<=1e4）个人的体重w（<=1e9）和椅子的承重m（<=2e9），输出最少需要的椅子数量（可以2个人坐一把椅子）
题解：先排序，最轻和最重的人组合做一把，如果这种组合都坐不下那么继续找倒数第二重的，最重的自己一把椅子
AC代码：（双指针）
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstdio>
using namespace std;
int n;
long long int m;
int num[100000]={0};
int main(){cin>>n>>m;for (int i=0;i<n;i++) cin>>num[i];sort(num,num+n);int ans=0;int i=0,j=n-1;for (;j>=i;){if (num[i]+num[j]<=m) {ans++;i++;j--;}else {ans++;j--;}}cout<<ans;
}E - Zydsg的自行车
题意：原题为过河问题，只有一条船，有n个人要过河，不同的人过河时间不同，两个人同时过河按最大时间的那个算，求将所有人都运过河的最短时间（船过河后还需一个人开回来）
题解：为了使时间最少，每次将用时最多的两个人运过河时有两种策略，设用时最少和最多的四个人过河时间依次是a，b，c，d；一种方案是a+2*b+d（a，b做中介），一种是2*a+c+d（a做中介），两者取耗时最少的那个即可；最后剩下可能有3个人（用时为a+b+c）,两个人（b）和最开始时只有一个人（a）的情况，分类讨论下即可
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
// freopen("input.txt","r",stdin);int T;scanf("%d",&T);while (T--){int n;scanf("%d",&n);int a[n];for (int i=0;i<n;i++) scanf("%d",&a[i]);sort(a,a+n);int ans=0;int i;for (i=n-1;i>=3;i-=2){int t=a[i]+2*a[1]+a[0],c=a[0]*2+a[i]+a[i-1];ans+=min(t,c);}if (i==1) ans+=a[1];else if (i==2) ans+=(a[0]+a[1]+a[2]);else if (i==0) ans=a[0];printf("%d\n",ans);}
} ps：只有全局变量才会自动初始化为0，在函数内定义的变量不会初始化（包括main函数）！！！
F - Alice and Bob
题意：矩形覆盖问题，给你分别给Alice和Bob n（<=1e5）个矩形（有长和宽<=1e9），问A能覆盖B的矩形个数最多是多少
题解：先按长或宽排序，（假设是长）考虑怎样做才不会使矩形浪费，如A有9 13 和10 10，B有8 9和9 11如果按排序的顺序覆盖，A只能盖掉8 9而10 10不能覆盖9 11，所以需要尽量使A的矩形发挥最大价值，于是引入一个multiset把符合条件的B的矩形存起来，然后取出最大那个进行覆盖！
AC代码（multiset）：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=1e5+10;
struct m{int w,h;bool operator <(const m& a){return w<a.w ;}
}A[maxn],B[maxn];
multiset<int> C;
int main(){int n;scanf("%d",&n);while (n--){int t;scanf("%d",&t);for (int i=0;i<t;i++) scanf("%d%d",&A[i].w,&A[i].h);for (int i=0;i<t;i++) scanf("%d%d",&B[i].w,&B[i].h);sort(A,A+t);sort(B,B+t);multiset<int>::iterator it;int ans=0;C.clear();for (int i=0,j=0;i<t;i++){while (j<t&&B[j].w<=A[i].w) C.insert(B[j++].h);if (C.empty()) continue;it=C.upper_bound(A[i].h);if (it!=C.begin()){it--;C.erase(it);}else continue;ans++;}printf("%d\n",ans);}
}upper_bound 返回第一个大于参数的iterator的位置
lower_bound 返回第一个大于等于参数的iterator的位置
(据说如果用数组会超时)
G - Robot Vacuum Cleaner
题意：给定n个字符串(<=1e5),只包含s和h，给n个字符串排序使其组成一个字符串后其中的sh序列个数最大，s与h可不相邻
题解：从排列中取出相邻的两个字符串x和y，交换他们的位置只对这两个字符串产生影响，前面和后面的sh的数量不会改变，所以模仿冒泡排序的思想，只需依照价值将字符串排序即可（以s与h的比例为标准），若h==0则其价值最大，同时为了节约时间，对于每个字符串只需记录s和h的数量（每读取一个便使用结构记录）
AC代码：（struct）
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+100;
const long long Max=1e9;
typedef long long ll;
struct S{int num_h,num_s,temp;double p;friend operator <(const S a,const S b){return a.p>b.p;}
}A[maxn];
int cnt=0;void getin(int n){while (n--){char s[maxn];scanf("%s",s);int num_h,num_s,temp;double p=0;num_s=temp=0;num_h=0;for (ll i=0;s[i]!='\0';i++)if (s[i]=='s') num_s++;else {num_h++;temp+=num_s;}if (num_h==0) p=Max;else p=double (num_s)/num_h;A[cnt].num_h =num_h;A[cnt].num_s =num_s;A[cnt].temp =temp;A[cnt].p =p;
// cout<<A[cnt].num_h <<' '<<A[cnt].num_s <<' '<<A[cnt].p <<' '<<A[cnt].temp <<endl;cnt++;}
}
void getans(){sort(A,A+cnt);ll ans=0,num_s=0;for (long long int i=0;i<cnt;i++){ans+=num_s*A[i].num_h ;ans+=A[i].temp ;num_s+=A[i].num_s ;}cout<<ans;
}
int main(){int n;scanf("%d",&n);getin(n);getans();
}一份更为简洁的代码（却耗时更长？）：（可能是排序的标准不同）
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100100;
struct Node{int s, h;bool operator < (const Node &b) const{return (ll)s * b.h > (ll)b.s * h;}
}o[maxn];
char s[maxn];
int main(){int n; scanf("%d", &n);ll ans = 0;for(int i = 1; i <= n; i++){scanf("%s", s);int m = strlen(s);for(int j = 0; j < m; j++)if(s[j] == 's') o[i].s++;else ans += o[i].s, o[i].h++;}sort(o + 1, o + 1 + n);int cnt = 0;for(int i = 1; i <= n; i++){
// printf("%d %d\n", o[i].s, o[i].h);ans += (ll)o[i].h * cnt;cnt += o[i].s;}printf("%lld\n", ans);return 0;
}H - Tian Ji -- The Horse Racing
题意：田忌赛马问题，不过这次是n匹各种速度的马，赢一场比赛有200块，如何使赚的钱最多
题解：使用4指针，先排序，然后从田忌马的头尾和王马的头尾开始遍历，原则是使每一匹马发挥的价值最大，即大马能打得过大马就打，打不过时看小马，如果小马打得过小马就打，否则用田忌的小马对掉王的大马；也可以从小马开始看；注意有可能小马速度到最后和大马一样，这时不计算负的盘数；
AC代码（四指针）：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int t[1000+10];
int k[1000+10];
int main(){
// freopen("input.txt","r",stdin);int n;while (scanf("%d",&n)==1&&n){memset(t,0,sizeof(t));memset(k,0,sizeof(k));for (int i=0;i<n;i++) scanf("%d",&t[i]);for (int i=0;i<n;i++) scanf("%d",&k[i]);int t1=0,k1=0,tr=n-1,kr=n-1;sort(t,t+n);sort(k,k+n);int win=0,lose=0;while(t1<=tr){if (t[tr]>k[kr]) { tr--;kr--;win++;}else if (t[tr]<k[kr]){ lose++; t1++;kr--;}else if (t[tr]==k[kr]){if (t[t1]<k[k1]) { lose++; t1++;kr--;}else if (t[t1]>k[k1]) { t1++;k1++;win++;}else if (t[t1]==k[k1]) { if (t[t1]<k[kr]) lose++;t1++;kr--;}}}printf("%d\n",(win-lose)*200);}
}总结：贪心算法运用的条件是贪心的过程中不会对全局造成影响（与动态规划做区别），从而通过局部最优达到全局最优，用的标准是不浪费，最大化每一步产生的价值。
更多推荐
2018SCUACM Training 1 贪心解题报告
发布评论