Codeforces Round #143 (Div. 2) B

http://codeforces.com/problemset/problem/231/B

苦逼贪心被当成了搜索。。。

学习大牛代码:

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 #define MAXN 110
 8 int ans[MAXN];
 9 int n,d,l;
10 
11 int main()
12 {
13     while(scanf("%d%d%d",&n,&d,&l) != EOF)
14     {
15         int tmp=0;//奇数和与偶数和的差
16         for(int i=0;i<n;i++)
17         {
18             ans[i]=1;//最少为1
19             if(i%2==0)
20                 tmp++;
21             else
22                 tmp--;
23         }
24         for(int i=0;i<n;i++)
25         {
26             while(i%2==0 && tmp<d && ans[i]<l)//贪心
27                 ans[i]++,tmp++;
28             while(i%2==1 && tmp>d && ans[i]<l)
29                 ans[i]++,tmp--;
30         }
31         if(tmp != d)
32         {    
33             puts("-1");
34             continue;
35         }
36         printf("%d",ans[0]);
37         for(int i=1;i<n;i++)
38             printf(" %d",ans[i]);
39         puts("");
40     }
41     return 0;
42 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <stack>
 8 
 9 using namespace std;
10 
11 #define MAXN 110
12 int ans1[MAXN];
13 int ans2[MAXN];
14 int n,d,l;
15 
16 int main()
17 {
18     while(scanf("%d%d%d",&n,&d,&l)  != EOF)
19     {
20         bool flag=0;
21         memset(ans1,0,sizeof(ans1));
22         memset(ans2,0,sizeof(ans2));
23         int ansmin=(n+1)/2;
24         int ansmax=l*(n+1)/2;
25         int leftmax=ansmax,rightmax=ansmax-d;
26         int leftmin=ansmin,rightmin=ansmin-d;
27         if(rightmax<(n/2) || rightmin>l*(n/2))
28         {
29             puts("-1");
30             continue;
31         }
32         if(rightmax>=l*(n/2))
33         {
34             for(int i=0;i<(n/2);i++)
35                 ans2[i]=l;
36             leftmax=(n/2)*l+d;
37             for(int i=0;i<(n+1)/2;i++)
38                 ans1[i]=1;
39             leftmax-=(n+1)/2;
40             int i=0;
41             while(leftmax>l-1)
42             {
43                 ans1[i++]+=l-1;
44                 leftmax-=(l-1);
45             }
46             ans1[i]+=leftmax;
47         }
48         else
49         {
50             for(int i=0;i<(n/2);i++)
51                 ans2[i]=1;
52             rightmin-=(n/2);
53             if(rightmin<0)
54                 rightmin=0;
55             int i=0;
56             while(rightmin>l-1)
57             {
58                 ans2[i++]+=l-1;
59                 rightmin-=(l-1);
60             }
61             ans2[i]+=rightmin;
62             leftmin=0;
63             for(i=0;i<(n/2);i++)
64                 leftmin+=ans2[i];
65             leftmin+=d;
66             i=0;    
67             for(int i=0;i<(n+1)/2;i++)
68                 ans1[i]=1;
69             leftmin-=(n+1)/2;
70             while(leftmin>l-1)
71             {
72                 ans1[i++]+=l-1;
73                 leftmin-=(l-1);
74             }
75             ans1[i]+=leftmin;
76         }
77         printf("%d %d",ans1[0],ans2[0]);
78         for(int i=1;i<(n/2);i++)
79             printf(" %d %d",ans1[i],ans2[i]);
80         if(n%2)
81             printf(" %d",ans1[(n+1)/2-1]);
82         printf("\n");
83     }
84     return 0;
85 }