首页 > 代码库 > cf 732c

cf 732c

 1                       /* cf732c 错过的最少次数 _________________________________________________________________________________
 2                         
 3                           #include <iostream> 
 4                           #include <map> 
 5                           #include <cmath>
 6                           #include <vector>
 7                           #include <cstdio>
 8                           #include <string>
 9                           #include <cstring> 
10                           #include <algorithm>    
11                           using namespace std; 
12                           #define fir first
13                           #define sec second
14                           #define pb(x) push_back(x) 
15                           #define mem(A, X) memset(A, X, sizeof A)
16                           #define REP(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
17                           #define rep(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i)) 
18                           #define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e) 
19                           typedef long long LL;   
20                           typedef unsigned long long ull;
21                           typedef pair<long,long>  pll;     
22                           
23                           
24                           LL T,n;
25                           const int mod=1e9+7; 
26                           const int maxn=1e5+10;    
27                           int main()
28                           {
29                                freopen("in.txt","r",stdin); 
30                                //while(cin>>n)
31                                LL a[4];
32                                while(cin>>a[1]>>a[2]>>a[3])
33                                { 
34                                  LL ans=0; 
35                                  if(!(a[1]==a[2]&&a[2]==a[3]))
36                                  {
37 
38                                     sort(a+1,a+4);
39                                     if(a[3]==a[2])
40                                         ans=a[3]-1-a[1];
41                                     else 
42                                         ans=2*a[3]-a[2]-a[1]-2;
43                                    }
44                                     cout<<ans<<endl;
45                                  //REP(kase,1,T)  { }
46               
47                                }
48                             return 0;
49                           }
50               
51                          /*
52                             note    :   这题主要是分析,化简情况,对于任意一种给定的组合,其最优的情况必然在最大值长度(可以看成投影)或该长度加一的天数
53                                         ,在这一分析之后,进一步化简成两个最大(对其(b d s)排序后 从小到大分别为 b1 b2 b3 )的组合的情况,考虑三种可能的
54                                          情况(其最少次数始终为 b3-1-b2)。除了所有均相等的情况时为0,剩下的所有情况(最大的两个不相等,为的是保证投影在b3中)
55                                          都是可以完全转化(通过剪切移动等价转化)为相同的情况计算的 即 (b3-2)-b2 + (b3-2)-b1 .
56                             debug   : 
57                             optimize:
58                           */ 

 

cf 732c