codeforces #342 div 2 A. Guest From the Past

2016-02-07 · 1 min read · math

http://codeforces.com/contest/625/problem/A 题意：有n块钱，塑料瓶饮料a元一瓶，玻璃瓶饮料b元一瓶，退还玻璃瓶可以得到c元。问最多能买多少瓶饮料。思路：贪心。如果塑料瓶比玻璃瓶的实际价格便宜，那么一定买塑料瓶的，否则先买玻璃瓶，再用塑料瓶填。注意一些边界的判断。。

/* ***********************************************
Author :111qqz
Created Time :2016年02月07日 星期日 17时02分32秒
File Name :code/cf/#342/A.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6LL a,b,c,n;
 7int main()
 8{
 9	#ifndef  ONLINE_JUDGE 
10//	freopen("code/in.txt","r",stdin);
11  #endif

 1	cin>>n;
 2	cin>>a>>b>>c;
 3	LL ans=0;
 4	if (b-c>a)
 5	{
 6	    ans = n/a;
 7	}
 8	else
 9	{
10	    while (n-b>=b-c)
11	    {
12		LL tmp = (n-b)/(b-c);
13		ans += tmp;
14		n-=tmp*(b-c);

1	    while (n>=b)
2	    {
3		LL tmp =n/b;
4		ans +=tmp;
5		n-=tmp*(b-c);
6	    }

	ans +=n/a;
	}
	
	cout<<ans<<endl;

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}