题目链接:
https://vjudge.net/problem/POJ-2586
题目大意:
MS公司(我猜是微软)遇到了千年虫的问题,导致数据大量数据丢失。比如财务报表。现在知道这个奇特的公司每个月不是盈利就是亏损(废话),而且无论是盈利和亏损都有一个定值(亏少了它还不干
)。经过ACM组织的分析,在一年中任意连续的5个月,它都是亏损的,但是全年就不一定亏损了。现在给你盈利和亏损的定值s和d,请求出它一年能得到的最大利润!如果亏了,就输出Deficit!
思路:
一开始暴力一发,枚举12个月的状态,TLE。应该贪心,
每五个连续的月一定亏损,我们可以设每五个月亏损月数最少为x,这种情况下,如果x能保证让这五个月为亏损,这是满足题意的盈利最大值!
x只能为1,2,3,4,5。 在保证连续5个月都亏损的前提下,使得每5个月中亏损的月数最少。根据d和s的不同五种情况
x=1: ssssd,ssssd,ss d>4s 赢利10个月 10s-2d
x=2: sssdd,sssdd,ss 2d>3s 赢利8个月 8s-4d
x=3: ssddd,ssddd,ss 3d>2s 赢利6个月 6s-6d
x=4: sdddd,sdddd,sd 4d>s 赢利3个月 3s-9d
x=5: ddddd,ddddd,dd 4d<s 无赢利
然后直接判断输出即可
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int s, d; int main()
{
while(cin >> s >> d)
{
ll ans;
//如果四个月盈利小于一个月亏损 ssssdssssdss 答案是10s-2d
if( * s < d)ans = * s - * d;
//如果三个月盈利小于两个月亏损 sssddsssddss 答案是8s-4d
else if( * s < * d)ans = * s - * d;
//如果两个月盈利小于三个月亏损 ssdddssdddss 答案是6s-6d
else if( * s < * d)ans = * s - * d;
//如果一个月盈利小于四个月亏损 sddddsddddsd 答案是3s-9d
else if( * s < * d)ans = * s - * d;
//如果一个月盈利大于四个月亏损 dddddddddddd 答案是亏损
else ans = -;
if(ans < )cout<<"Deficit"<<endl;
else cout<<ans<<endl; }
return ;
}