oj记录 codeforces 1679 A. AvtoBus

题目描述

https://codeforces.com/contest/1679/problem/A

Spring has come, and the management of the AvtoBus bus fleet has given the order to replace winter tires with summer tires on all buses.

You own a small bus service business and you have just received an order to replace n tires. You know that the bus fleet owns two types of buses: with two axles (these buses have 4 wheels) and with three axles (these buses have 6 wheels).

You don’t know how many buses of which type the AvtoBus bus fleet owns, so you wonder how many buses the fleet might have. You have to determine the minimum and the maximum number of buses that can be in the fleet if you know that the total number of wheels for all buses is n.

题意

给出整数n，满足4x+6y=n（x、y为非负整数），求x+y的最小值和最大值（>=1）。若不存在，输出-1.

思路

• 首先n必须为偶数，且必须>=4。
• 既然n一定是偶数，不妨n/=2，问题变成2x+3y=n；
• 显然x+y的最小值为n/3,最大值为n/2(如果可以整除)
• 如果不能整除：
  当n%3=1，可以把一个3和余下的1 换成两个2，即ans=n/3+1;
  当n%3=2,就直接把余下的2 作为‘2’，ans也是n/3+1;
  同理：n%2=1时，把一个2和余下的1换为3，ans为n/2

code

#include
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
// const int mod=1e9+7;
// const int N;


void solv()
{
    ll n;
    cin>>n;
    if(n&1||n<4)cout<<-1<<'\n';
    else
    {
        n/=2;
        ll ans1,ans2;
        if(n%3==0)ans1=n/3;
        else ans1=n/3+1;
        ans2=n/2;
        cout<<ans1<<' '<<ans2<<'\n';
    }

}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
    {
        solv();
    }
    return 0;
}

注意与总结

-做题时没有考虑到可以用余数和2或3组合来换成合法的答案
（＞﹏＜）

知识补充