Chinaunix首页 | 论坛 | 博客

熟睡的企鹅finekill.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

zhln

  • 博客访问： 1547058
  • 博文数量： 327
  • 博客积分： 10000
  • 博客等级： 上将
  • 技术积分： 3556
  • 用 户 组： 普通用户
  • 注册时间： 2005-04-05 21:28
个人简介

东黑布衣，流浪幽燕。 真诚善良，值得信赖。

文章分类

全部博文（327）

我的朋友
推荐博文
相关博文
20161019 ADV

分类： BSD

2016-10-19 23:50:27


  1. // 20161019.c
  2. //
  3. #include <stdio.h>
  4. #include "stdafx.h"
  5. int T,N,K;
  6. int a[2][8]={0};
  7. int c[8]={0};
  8. int b[8]={0};
  9. int result;
  10. int lmin;
  11. int lmax;
  12. int line_min()
  13. {
  14.     int j=0;
  15.     int inflate=0;
  16.     int deflate=0;
  17.     while(j<N){
  18.         inflate += a[0][j];
  19.         deflate += a[1][j];
  20.         j+=1;
  21.     }
  22.     if(inflate>=deflate)
  23.         return 0;
  24.     else
  25.         return deflate-inflate;
  26. }
  27. int line_max()/*由于前次试验的剩余气压最少为0，所以用K依次减去充气气压，取得最小值也就是充气气压的最大值*/
  28. {
  29.     int j=0;
  30.     lmax=K;
  31.     while(j
  32.         lmax = ((K-a[0][j])
  33.         j+=1;
  34.     }
  35.     return lmax;
  36. }
  37. void combination(int step)
  38. {
  39.     int min;
  40.     //int max;
  41.     int present;
  42.     int i;
  43.     int tmp;
  44.     int flag;
  45.     if(step==N){
  46.         //max=K-a[0][c[0]];
  47.         tmp=a[1][c[0]]-a[0][c[0]];
  48.         min = (tmp>0)? tmp:0;
  49.         min = (min<lmin)? lmin:min;
  50.         while(min<=lmax){/* max => lmax*/
  51.             flag=0;
  52.             present=min;
  53.             for(i=0;i<N;i++){
  54.                 if(present+a[0][c[i]] > K){
  55.                     flag=1;
  56.                     break;
  57.                 }
  58.                 if(present+a[0][c[i]]-a[1][c[i]] < 0){
  59.                     min += (a[1][c[i]] - a[0][c[i]]);
  60.                     break;
  61.                 }
  62.                 present = present + a[0][c[i]] - a[1][c[i]];
  63.             }
  64.             if(i==N){
  65.                 if(-1 == result)
  66.                     result = min;
  67.                 else
  68.                     result = (result>min)? min:result;
  69.                 return;
  70.             }
  71.             else{
  72.                 if(flag==1)
  73.                     return;
  74.                 continue;
  75.             }
  76.         }
  77.         return;
  78.     }
  79.     for(i=0;i<N;i++){
  80.         if(b[i]==0){
  81.             c[step]=i;
  82.             b[i]=1;
  83.             combination(step+1);
  84.             b[i]=0;
  85.         }
  86.     }
  87.     return;
  88. }
  89. int _tmain(int argc, _TCHAR* argv[])
  90. {
  91.     freopen("20161019ibak.txt","r",stdin);
  92.     //freopen("20161019o.txt","w",stdout);
  93.     //setbuf(stdout,NULL);
  94.     int t;
  95.     int i;
  96.     int j;
  97.     scanf("%d", &T);
  98.     for(t=0;t<T;t++){
  99.         scanf("%d %d",&N,&K);
  100.         for(i=0;i<2;i++){
  101.             for(j=0;j<N;j++){
  102.                 scanf("%d", &a[i][j]);
  103.             }
  104.         }
  105.         result=-1;
  106.         lmin=line_min();
  107.         lmax=line_max();
  108.         combination(0);
  109.         printf("#%d %d\n",t,result);
  110.     }
  111.     return 0;
  112. }
  113. /* in
  114. 题目的背景是通过为轮胎充气，放气而进行产品验收。一充一放为一次，共进行N次，
  115. 轮胎的最大承受气压为K，最小为0，超出K或者低于0轮胎将损坏，
  116. 现在要求出某一个排列，使轮胎的初始气压为最小。
  117. 5
  118. 3 100
  119. 75 45 80
  120. 30 55 95
  121. 2 100
  122. 65 90
  123. 20 30
  124. 5 150
  125. 35 105 100 45 75
  126. 115 75 55 35 105
  127. 7 150
  128. 70 95 15 65 85 75 55
  129. 106 80 10 90 115 110 45
  130. 8 200
  131. 35 30 50 80 70 15 10 40
  132. 70 20 20 85 65 40 25 50
  133. */
  134. /* out
  135. 15
  136. -1
  137. 25
  138. -1
  139. 45
  140. */


阅读(1417) | 评论(1) | 转发(0) |
0

上一篇：数组模拟链表

下一篇：Visual Studio Tips

给主人留下些什么吧！~~

zhln2016-10-20 10:19:59

现在我也不确定lmax是否正确，留待思考确定。稳妥起见就用max罢

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6