小白月赛25（小白版）

A AOE还是单体？ 题目链接

https://ac.nowcoder.com/acm/contest/5600/A

解题思路

说实话，这个题靠着惯性思维就可以想出贪心思路（其实，我都没感觉这是个贪心，以为顶多算个思维题）。AOE技能是范围攻击，造成群体伤害，就看AOE的伤害-能耗比，与单体攻击的伤害-能耗比的大小。举个例子，五只怪物，一次AOE消耗3mp时，我们需要先用AOE消耗吧，因为要是用单体攻击，对每个怪物造成1点伤害需要5mp，而AOE攻击只消耗3mp，对应到伤害-能耗比上，AOE：5/3，单体：5/5，AOE的效率比单体高，先用AOE。 问题来了，AOE不可能一直效率比单体高啊，什么时候AOE就不如单体了？举个例子，五只怪物，一次AOE消耗10mp，对应到伤害-能耗比上，AOE：5/10，单体：5/5，这时候AOE就不如单体来的实在了，所以选单体攻击。 总结一下会发现， 当x（即一次AOE消耗xmp）> 现存怪物数量时，我们使用一技能（即单体攻击）。不理解的话我们用数据说话，假设num代表现存怪物数量（因为一次AOE对全体怪物造成一点伤害，所以总伤害=num*1=num），那么对应到伤害-能耗比上，AOE：num/x，单体：num/num，毋庸置疑，单体效率永远是1，而此时的AOE效率1=单体效率，因此二技能为佳。

简化实现

基本思路都有了，与思路同等重要的还有代码的实现（因为其实解题思路只是为代码实现提供了个大框架，与真正的实现还是有不小的区别的） 思考一下，我们能不能先算出“把全部怪物都消灭所使用的AOE消耗的全部mp之和”，再算出“把全部怪物都消灭所使用的单体技能消耗的全部mp之和”，两者之和就是消耗的全部mp。为保证消耗尽量少的mp，我们就得判断一下AOE的效率是不是比单体高，高了才能用，要不然还不如用单体伤害呢。 我们去按照怪物的血量从小到大排序，判断一下现存怪物数量时，AOE的效率是不是高，如果AOE效果好，那就多次使用AOE直接把血量最少的怪物消灭，因为如果不使用多次把当前怪物消灭，现存怪物数量不会减少，再比较现存怪物数量和x大小的时候，还是要AOE，所以不如直接干掉当前这个怪物，让现存怪物数发生改变。 当遍历排好序的怪物，现存数量到达x=现存的时候，以后就可以使用单体了，因为AOE效率不如单体高了。 其实，算出了“把全部怪物都消灭所使用的AOE消耗的全部mp之和”，也就是遍历到x=现存数量的时候，就不需要再继续遍历，求“把全部怪物都消灭所使用的单体技能消耗的全部mp之和”了。所有现存怪物的剩余血量之和就是我要使用单体攻击的次数，在数值上也等于单体攻击消耗的mp之和。所以，我们就在输入的时候累加算出全部怪物的总血量，拿总血量减去AOE造成的伤害就是所有现存怪物的剩余血量，即单体攻击消耗的mp。 （这就是代码实现的一点小技巧）

AC代码

#include
#define ll long long
using namespace std;
const int N=2e5+10;
int blood[N];
int main(){
 	int n,x;
 	cin>>n>>x;
 	ll sumblood=0;//记录所有怪物的总血量，用于减去AOE造成的伤害，求得单体攻击的次数
 	for(int i=1;i>blood[i];
  		sumblood+=blood[i];
 	}
   
 	sort(blood+1,blood+n+1);
 
 	ll num=n,summp=0;//num表示现存怪物数目，summp表示AOE所消耗的mp之和

 	for(int i=1;iy;
  		a[x].push_back(y);
  		a[y].push_back(x);
 	}
 	for(int i=1;in;

/*
    	//方法1
 	ll ans=1;
 	for(int i=1;i>a[i];
 	for(int i=1;i>b[i];
 	for(int i=1;i>c;
 	double ans=-1;
 	double l=0,r=1e9;
 	for(int i=1;i=c) r=x,ans=x;
  		else l=x;
 	}
 	printf("%.7lf",ans);
}

补充

想补充的东西挺多的。 1.首先说一点（吐槽），题目给的样例有问题，输出14位，开始也输出的14位，也AC了。看了大佬的题解，他们都输出的7位，应该是出题人笔误，大家自己注意就好了。 2.对比一下大佬代码

#include
#define ld long double
using namespace std;
int a,b,c;
ld f(ld l,ld r){ 
 	if(r-l=c) return f(l,x);
 	else return f(x,r);
}
int main(){
 	cin>>a>>b>>c;
 	printf("%.7Lf",f(1,c));
}

讲一下，大佬用的是递归难免会比我的代码跑的慢点。也就是说其实二分有两种方式，一种是二分达到一定次数结束，另一种是误差小于esp的时候结束，第一种方法适用于规定的误差很小或者并不是以误差判断结束的情况，相对普遍；第二种可能在有的情况下比较合适。通过“二分达到一定次数结束”的方式，为什么就进行100次就能找出分界点？二分是log级别的，每次折半，比如这道题范围是0~1e9，所以进行100次意味着每次循环都除以2，除了100次2，也就是除了2^ 100，int范围是2^ 32，这样你就明白为什么二分一百次完全够了吧。大佬用的方法，要注意两点，一是要用long double（第一次听说），double无法AC，而我的代码double就能过（不知道为什么）；二是eps为1e-8（eps就是误差） 3. 一些私货，自己百度的。 double有效的小数位是15位，long double有效的小数位是18位（不同编译器不一样，我的编译器就是跟double一样的精度）。再就是注意long double的输出%Lf，L必须大写，小数位个数的输出什么的跟其他类型的一样。

总而言之，太简单了，也太奇怪了。

H 神奇的字母（二） 题目链接

https://ac.nowcoder.com/acm/contest/5600/H

解题思路

（copy的大佬的，刚做的时候感觉这是个水题啊，这应该就是我和大佬之间的差距之一。看了大佬题解才发现，大佬说的这几个我还真不知道，于我而言，从中学到东西其实也不能算水题）

知识点：无 思路：这道题想更多的考察大家对“若干组输入”的处理方式，可以扫描空格回车。主要的解决方法有以下几种： ①while(cin>>str) ②while(scanf("%s",str)!=EOF) //EOF可以用-1代替。 ③while(gets(str)!=NULL) 第一个是c++写法，后两个是C语言写法。注意对应的头文件即可（或使用万能头文件）

我稍微讲一下，cin输入string类型的时候还是遇到tab，空格，回车等结束一个字符串的输入，while(cin>>str)好像是什么重载运算符之类的，我还没自学明白，所以不多讲这个了。记住的话就是输入str成功cin就返回非零值，输入失败就返回0。体现在这个本题样例的过程里就是，输入第一个字符串ranko，遇到空格，输入成功，进行while内部的操作，接着再次cin>>str，sekai，遇到空格，输入成功……就是这么个过程。

再补充一点，有同学可能纳闷怎么结束输入啊，为什么一直没有输出啊。 你只需要摁ctrl+z就能结束输入了。（本题注意一点，输入完样例的第二行的时候要先输入一个回车表示最后一个字符串输入成功且结束，再摁ctrl+z方可结束）

AC代码

我的代码输入不是用的大佬的方法，推荐用大佬的，大佬的可能好点。

#include
using namespace std;
const int N=30;
int cnt[N],ans,maxx;
int main(){
 
 	char ch;
 	while(~scanf("%c",&ch)){
 	if(ch==' ') continue;
  	if(ch=='\n')continue;
  	int id=ch-96;  
  	cnt[id]++;
  	if(cnt[id]>maxx){maxx=cnt[id];ans=id;} 
 	}
	// cout