【赛时·8】AGC-027

日常AGC坑……还好能涨Rating

+传送门+

◇ 简单总结

感觉像打多校赛一样，应该多关注一下排名……考试的时候为了避免影响心态，管都没有管排名，就在那里死坑B题。最后还剩十几分钟的时候发现大家都把C题AC了，B题空了一大堆。后来事实也证明了C题比B题简单。

◇ 题目&解析

◆A题◆ Candy Distribution Again ❄模拟❄

·【题意】

老师要将x颗糖分给n个孩子（恰好分完）。当第i给孩子得到恰好a[i]颗糖时，他会感到快乐。问如何给孩子分糖使得快乐的孩子最多，输出最多有多少个孩子感到快乐。

·【解析】

尽量先把糖分给a[i]小的孩子，这样可以使得到恰好a[i]颗糖的人数尽量大。但是注意特判当每个人都分到a[i]颗糖后还剩有糖时，因为要把糖分完，则必定有一个人得到的糖多余a[i]，要把答案-1。

·【源代码】

/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,tot;

int chi[105];

int main(){

	scanf("%d%d",&n,&tot);

	for(int i=0;i<n;i++)

		scanf("%d",&chi[i]);

	sort(chi,chi+n);

	int ans=0;

	for(int i=0;i<n;i++)

		if(chi[i]<=tot){

			ans++;

			tot-=chi[i];

		}

		else{

			tot=0;

			break;

		}

	if(tot) ans--;

	printf("%d\n",ans);

	return 0;

}

◆B题◆ Garbage Collector ❄数学+模拟❄

 · 【题意】

数轴的正半轴上（>0，且垃圾位置相同）有n个垃圾，分别位于 x1,x2,...,xn 。有一个机器人在原点，每次可以移动一步。原点还有一个垃圾桶，机器人要把垃圾捡到垃圾桶里。机器人可以同时拿多个垃圾，当它拾起一个垃圾或者把它携带的所有垃圾丢到垃圾桶里时，需要消耗X点能量。且当机器人拿起k个垃圾时，每移动一个单位就需要消耗(1+k)2点能量。求出机器人把所有垃圾捡回垃圾桶所需要的最小能量。注意：机器人只能把垃圾丢进垃圾桶里，不能放在数轴的其他位置。

第一行输入n；第二行输入 n 个整数表示垃圾的位置，从左到右依次输入。

机器人把所有垃圾捡到垃圾桶里的最小花费。

· 【解析】

考试的时候就没有考虑过数学暴力展开平方项……看了题解恍然大悟QwQ

有几个结论很容易想到（但是我也不知道怎么证明）：

每次捡的垃圾数量应该是一样的（除了最后一次可能捡得少一些）；（某Tiw告诉我这个不需要证明（https://blog.csdn.net/Tiw_Air_Op1721））

最好取连续的一段垃圾，并且先到达离原点最远的垃圾，然后折返回来捡剩下的垃圾。

那么我们就可以先确定我们要从起点出发多少次来把垃圾捡完。那么我们每次就要捡（n/k）个垃圾然后返回原点，当然最后一次可能捡得少一点。

假设我们某一次从原点出发要捡的连续一段垃圾的位置为  pos[1~m]，再算上原点的坐标pos[0]=0。则捡这些垃圾的花费为：

[1+(m+1)²]·(pos[1]-pos[0]) + [1+(m-1+1)²]·(pos[2]-pos[1]) + [1+(m-2+1)²]·(pos[3]-pos[2]) + .... + [1+(2+1)²]·(pos[n-1]-pos[n-2]) + [1+(1+1)²]·(pos[n]-pos[n-1])

那么上式中关于pos[i]的花费为：

cst[i] = [1+(m-i+1+1)²]·pos[i] - [1+(m-i-1+1+1)²]·pos[i] = pos[i]·[(m-i+2)² - (m-i+1)²] = pos[i]·[(2m-2i+3)·1] = pos[i]·(2m-2i+3)

然后就可以得出一次的总花费为：fcst[i]=cst[1~m]

所以所有的花费为 now=fcst[1~n/k]

（只可意会不可言传）

· 【源代码】

/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=int(2e5);

int n;

ll X;

ll dst_sum[N+5];

int main(){

    scanf("%d%lld",&n,&X);

    for(int i=1,dst;i<=n;i++){

        scanf("%d",&dst);

        dst_sum[i]=dst_sum[i-1]+dst;

    }

    ll ans=ll(1e18);

    for(int k=1;k<=n;k++){ //决定丢多少个垃圾

        ll now=0,cof=1;

        for(int i=n;i>=1;i-=k){

            now+=(dst_sum[i]-dst_sum[max(i-k,0)])*max((cof+=2),5ll);

            if(now>ans) break; //最优性剪枝

        }

        now+=(n+k)*X;

        ans=min(ans,now);

    }

    printf("%lld\n",ans);

    return 0;

}

◆C题◆ ABland Yard ❄二分图+环+DFS❄

非常有意思+1……我又写了一篇Blog