本题题目链接：http://poj.org/problem?id=2586
本题的知识点是贪心算法，题目大意如下：某数组内存储12个数，数的取值只有s和-d。其中s与d皆为正数。该数组满足以下性质：每在数组上连续取5个数值加和皆小于0。现问能否选取合适数量的s与-d并将它们排在合适的位置，实现所有12个数的加和最大且大于0。如果不可实现，便输出Deficit。
想要实现可能的最大值，则必须保证整数的个数应尽可能多。为简化思考过程，我们不妨将范围分割为2个5元素数组和1个2元素数组，如图所示：
详细考虑，我们力图实现全局最大，则应该尽力实现局部最大，所以我们假设该局部数组内原先填充的都是整数，我们逐个减少正数的个数并不断增加负数的个数。直到某个临界点，即刚刚实现该子结构为负。这样，我们便得到了我们的最优子结构。
根据规律，前2个5元素数组的形式都是相同的，唯一的不同就是最后两个元素的取值，这取决于我们求出的最优子结构的前两个数字的值。这两个数字的取值只有两种情况：一种是一正一负，一种是两个数字都是正数（不会出现都是负数的情况）。而正数因为被我们排在最前部的原因，我们可以根据正数的数量判断这两个数字的情况：只有1个正数的话说明是一正一负，有两个或以上的正数的话说明两个都是正数。
代码如下：
1 #include2 int main (int argc,char *argv[]){ 3 long long int s=0; 4 long long int d=0; 5 while(scanf("%lld%lld",&s,&d)!=EOF){ 6 int num=5; 7 for (;num>0;num--){//反向遍历实现最优子结构的查找 8 if (s*num-d*(5-num)<0) 9 break; 10 } 11 int x_final=0; 12 int y_final=0; 13 if (num==1){//根据正数的数量判断最后两个数的情况 14 x_final=num*2+1; 15 y_final=(5-num)*2+1; 16 } 17 if (num>=2){ 18 x_final=num*2+2; 19 y_final=(5-num)*2; 20 } 21 long long int final=s*x_final-d*y_final; 22 if (final0) 23 printf("Deficit\n"); 24 else 25 printf("%lld\n",final); 26 } 27 return 0; 28 }
Original: https://www.cnblogs.com/johnsonstar/p/15991734.html
Author: Johnson-Hugo
Title: 学习随笔——POJ题目2586：Y2K Accounting Bug解答
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583999/
转载文章受原作者版权保护。转载请注明原作者出处！