H.Exchange for Cola
题目大意：开始的时候你有 n 个瓶盖， 并且每 a 个瓶盖可以换 b 瓶可乐(a > b)，由于开始时可能瓶盖数量不够，你可以向别人借一些瓶盖，但最后一定要把借的瓶盖全部还回去。问你最多可以喝多少瓶啤酒？
解题思路：这样的题是想法题，分析如下：假设最多可以换 x 次啤酒，因为每换一次啤酒瓶盖数量就会少（a - b）个 ，而你原来有n个瓶盖，假设总共借了 y 个瓶盖，要想最后把 y 个瓶盖全部换回去，那么必须满足如下不等式：
n + y - x * ( a - b ) >= y -> x <= n / ( a - b )
所以， 最后答案就是 x * b 。
Ps ：此题数据范围会超 int ，所以 要用 long long 。
请看代码：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
int main()
{
long long a , b , n ;
while (cin >> n >> a >> b)
{
long long c = a - b ;
long long x = n / c ;
long long ans = x * b ;
cout << ans << endl ;
}
return 0 ;
}
I.Dr. Zomboss's Revenge
题目大意：给你一个 n * m 的网格和 t 种植物 ， 每一种植物（编号为 i）有三个参数 ci 、bi 、ai , 其中 ci 代表数量，题目保证所有 ci 的和 等于 n * m ，现在让你放置植物，每个网格放置一个植物，敌人有一个炸弹，会随机的扔到某一行，紧接着这一行的植物会全部销毁，被销毁的行有一个值 sum = 所有（cnt[ i ] - bi） * ai 的和 , 其中，cnt[ i ] 表示该行中第 i 种植物的数量，注意：当cnt[
i ] <= bi 时 ， cnt[ i ] - bi 的值记为 0 。让你合理的放置植物使 sum的平均值最小。
解题思路：此题也是一道想法题，放置植物的最好方式就是，对于每一种植物来说，先每行放置一个，当行放满时，开始放 下一列，继续上述步骤，直至把该植物放完。
请看代码：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 50 ;
int G[MAXN][MAXN] ;
int cnt[MAXN] ;
int ans ;
int n , m ;
int t ;
struct Node
{
int c ;
int b ;
int a ;
} s[MAXN] ;
void init()
{
int i ;
for(i = 0 ; i < t ; i ++)
{
scanf("%d%d%d" , &s[i].c , &s[i].b , &s[i].a) ;
}
}
void solve()
{
mem(G , -1) ;
ans = 0 ;
int i , j ;
int ti = 1 ;
int tj = 1 ;
for(i = 0 ; i < t ; i ++)
{
if(s[i].c <= s[i].b) // 当植物的总数量 < b 时，显然不用考虑
{
continue ;
}
int x = s[i].c ;
while (x --)
{
if(ti > n )
{
ti = 1 ;
tj ++ ;
}
G[ti ++][tj] = i ;
}
}
for(i = 1 ; i <= n ; i ++)
{
mem(cnt , 0) ;
for(j = 1 ; j <= m ; j ++) // 统计每一行各个种类的数量
{
if(G[i][j] != -1)
cnt[ G[i][j] ] ++ ;
}
for(int k = 0 ; k < t ; k ++)
{
if(cnt[k] > s[k].b)
{
ans += (cnt[k] - s[k].b) * s[k].a ;
}
}
}
printf("%.3f\n" , ans * 1.0 / n) ;
}
int main()
{
while (scanf("%d%d%d" , &n , &m , &t) != EOF)
{
init() ;
solve() ;
}
return 0 ;
}