【bestcoder #34】ABC题解

【bestcoder #34】ABC题解

Go to movies

   Accepts: 624    Submissions: 1526  Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) 问题描述

寒假啦！为了打发无聊的时光，同时增进男女之间的感情，身为班长的乐乐打算带领大家看电影。
寒假时期的电影票往往很贵，于是乐乐决定团购。

输入描述

有多组测试数据，大约20组。
输入包含多组数据，对于每组数据，第一行包含两个整数n和m，n表示有多少学生参加，m表示提供团购的电影院数。
接下来m行，每行两个整数a和b，表示每个电影院提供的团购方案，可以用b元买a张票。(1≤n,m,a,b≤100)

输出描述

对于每组数据，选择一个电影院，输出最少的花费。

输入样例

3 2
2 2
3 5

输出样例

4

Hint

样例解释，可以团购两次电影院1，花费4.

分别计算每个电影院的团购价格，输出最小。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,ans;
int main()
{while (scanf("%d%d",&n,&m)!=EOF){ans=inf;for (int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);int k=(n/a)*b;if (n%a) k+=b;ans=min(ans,k);}cout<<ans<<endl;}return 0;
}

Building Blocks

   Accepts: 105    Submissions: 1415  Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) 问题描述

看完电影后，乐乐回家玩起了积木。
他已经搭好了n堆积木，他想通过调整积木，使得其中有连续W堆积木具有相同的高度，同时他希望高度恰好为H。
乐乐的积木都这了，也就是说不能添加新的积木，只能移动现有的积木。
他可以把一个积木从一堆移动到另一堆或者新的一堆，但是不能移动到两堆之间。比如，一次移动之后，"3 2 3" 可以变成 "2 2 4" 或者 "3 2 2 1",但是不能变成"3 1 1 3".
请你帮他算算，需要移动的最少积木数。

输入描述

有多组测试数据，大约100组。
第一行三个整数，n，W，H，n表示有多少堆积木。
第二行n个元素，表示这n座积木的高度。
所有数据的范围[1,50000];

输出描述

输出最少需要移动的次数，如果无法完成输出-1。

输入样例

4 3 2
1 2 3 5
4 4 4
1 2 3 4

输出样例

1
-1

Hint

样例解释：把第3座积木上的一个积木移动到第1座上，前3座积木的高度就变成了2 2 2，就得到了一个3*2（积木必须是连续的W堆）。

不难发现一个区间满足条件需要移动的最少次数就是把高的变矮的总操作数和矮的变高的总操作数的较大值。

但是题中说可以在两侧新建堆，因此在两侧各加上w个h=0的堆即可。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define M 200000+5
#define LL long long
using namespace std;
int d[M],h[M];
int main()
{freopen("t.in","r",stdin);int n,w,H;while (scanf("%d%d%d",&n,&w,&H)!=EOF){LL cnt=0;for (int i=1;i<=w;i++)h[i]=0,d[i]=H-h[i];for (int i=w+1;i<=w+n;i++){scanf("%d",&h[i]);cnt+=h[i];d[i]=H-h[i];}for (int i=w+n+1;i<=w+n+w;i++)h[i]=0,d[i]=H;if (cnt<(LL)(1LL*w*H)) {puts("-1");continue;}LL ans=1LL*H*w;LL z=ans,f=0;for (int i=w+1;i<=w+n+w;i++){if (d[i-w]>0) z-=d[i-w];else f-=(-d[i-w]);if (d[i]>0) z+=d[i];else f+=(-d[i]);ans=min(ans,max(f,z));}cout<<ans<<endl;}return 0;
}

Building Blocks Ⅱ

   Accepts: 8    Submissions: 253  Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) 问题描述

乐乐又开始搭积木了。
他想在昨天搭完的积木上，重新搭建，使得其中有连续W堆积木具有相同的高度，同时他希望高度最少为H。
乐乐的积木都这了，也就是说不能添加新的积木，只能移动现有的积木。
他可以把一个积木从一堆移动到另一堆或者新的一堆，但是不能移动到两堆之间。比如，一次移动之后，"3 2 3" 可以变成 "2 2 4" 或者 "3 2 2 1",但是不能变成"3 1 1 3".
请你帮他算算，当搭建的高度h为多少时，需要移动的积木最少，如果有多个h满足条件，输出h的最大值。 

输入描述

有多组数据，大约100组。
对于每组数据,第一行三个整数n、W、H。
第二行n个元素，表示n座积木的高度。
题目中所有数据的范围[1,50000];

输出描述

输出两个整数，第一个数表示搭建的高度h，第二个数表示需要移动的最小积木数。
如果有多个h满足使得移动步数最少，输出h的最大值。
如果不能形成高度最少为H的连续的W堆积木，输出-1。

输入样例

3 3 2
4 2 4
4 3 4
6 6 3 10
4 4 4
1 2 3 4

输出样例

3 2
5 2
-1

Hint

样例一解释，一种可行的方案是从第一堆移动一个到第二堆，从第三堆上面移动一个放到右边，每堆个数变成 3 3 3 1。最少移动2次。
样例二解释，把第一座和第二座积木上的一个积木移动到第三座积木上，得到3*5。

ans=max(sigma(hi-h),sigma(h-hj)) hi>=h,hj<h

当h增大前者减小，当h减小后者减小。

要让ans最小则让前者等于后者：

sigma(hi-h)=sigma(h-hj)

h=sigma(hi)/w  hi是该区间的全部h，也就是区间的平均数。

当然也可能是h+1,或者H。

确定了h之后，需要统计区间大于h和小于h的高度和，用一个树状数组即可~