CV的人有福啦!YTU贪心训练2(部分注释,更新ing)

------------恢复内容开始------------

无聊做了做(虽然第一题被水了)

1743 Problem A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100010;
 4 int n,k,s[N],a[N],sum[N],ans,x,y,res;
 5 int main()
 6 {
 7     cin>>n>>k;
 8     for(int i=0;i<n;i++) cin>>a[i];
 9     sort(a,a+n);
10     while(y<n)
11     {
12         s[x]+=a[y],sum[x]+=s[x];
13         x++,y++;
14         if(x==k) x=0;
15     }
16     for(int i=0;i<k;i++) res+=sum[i];
17     printf("%.0lf",(double)res/n);
18     return 0;
19 }

1757 Problem B

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100010;
 4 struct node
 5 {
 6     int x,y;
 7     bool operator<(const node &w)const
 8     {
 9         return x<w.x;
10     }
11 }range[N];
12 int n,res;
13 int main()
14 {   
15     cin>>n;
16     for(int i=0;i<n;i++)
17     {
18         int a,b;
19         cin>>a>>b;if(a>b) swap(a,b);
20         range[i]={a,b};
21     }
22     sort(range,range+n);
23     int ed=range[0].r;
24     for(int i=1;i<n;i++)
25     {
26         if(range[i].x<=ed) res++;
27         else ed=range[i].y;
28     }
29     cout<<res;
30     return 0;
31 }

1002 Problem C

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100010;
 4 int n,m;
 5 double res;
 6 struct node
 7 {
 8     double t,v,x;
 9     bool operator<(const node &w)const
10     {
11         return x>w.x;
12     }
13 }f[N];
14 int main()
15 {
16     while(cin>>n>>m&&n!=0)
17     {
18         memset(f,0,sizeof f);
19         res=0;
20         for(int i=1;i<=n;i++) cin>>f[i].t>>f[i].v,f[i].x=f[i].v/f[i].t;
21         sort(f+1,f+n+1);
22         for(int i=1;i<=n;i++)
23         {
24             if(m-f[i].t<0)
25             {
26                 res+=f[i].x*(double)m;
27                 break;
28             }
29             else m-=f[i].t,res+=(double)f[i].v;
30         }
31         printf("%.2lf\n",res);
32     }
33     return 0;
34 }

2461 Problem D

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100;
 4 int n,a[5]={1,3,9,27,81},f[N];
 5 string s;
 6 bool vis;
 7 void dfs(int st,int t,int num,int step)
 8 {
 9     if(vis) return;
10     if(num==t)
11     {
12         for(int i=0;i<step+1;i++)
13         {
14             if(i<step) cout<<f[i]<<s[i];
15             else cout<<f[i];
16         }
17         vis=true;
18     }
19     if(num>t) for(int i=st-1;i>=0;i--)
20     {
21         f[step+1]=a[i],s[step]='-';
22         dfs(i,t,num-a[i],step+1);
23         f[step+1]=0;
24     }
25     else for(int i=st-1;i>=0;i--)
26     {
27         f[step+1]=a[i],s[step]='+';
28         dfs(i,t,num+a[i],step+1);
29         f[step+1]=0;
30     }
31     return;
32 }
33 int main()
34 {
35     cin>>n;
36     int p;
37     if(n<=81)
38     {for(int i=0;i<5;i++) if(a[i]>=n){p=i;break;}}
39     else p=4;
40     f[0]=a[p];
41     dfs(p,n,a[p],0);
42     return 0;
43 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100000;
 4 int n,k,res,a[5]={1,3,9,27,81};
 5 int main()
 6 {
 7     cin>>n;
 8     if(n<=81)
 9     {for(int i=0;i<5;i++) if(a[i]>=n) {k=i;break;}}//找到最接近的
10     else k=4;
11     res=a[k];
12     cout<<a[k];
13     int num=0;
14     while(res!=n)
15     {
16         int x,c;
17         for(int i=0;i<4;i++)
18             if(a[i]<=abs(n-res)&&a[i+1]>=abs(n-res)) {x=i;break;}//找到处于这之间的
19         if(abs(a[x]-res+n)>abs(a[x+1]-res+n)) c=x+1;//找到最接近的那个
20         else c=x;
21         if(res>n) cout<<'-'<<a[c],res-=a[c];//判断
22         else cout<<'+'<<a[c],res+=a[c];
23     }
24     return 0;
25 }

3155 Problem I

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a,b,c,d,e,f,res;
 4 int op[4]={0,5,3,1};
 5 int main()
 6 {
 7     while(cin>>a>>b>>c>>d>>e>>f&&(a+b+c+d+e+f)!=0)
 8     {
 9         res=f+d+e+(c+3)/4;
10         int x=d*5+op[c%4];//先算2x2的箱子
11         if(b>x) res+=(b-x+8)/9;
12         int y=36*res-36*f-25*e-16*d-9*c-4*b;
13         if(a>y) res+=(a-y+35)/36;
14         cout<<res<<endl;
15     }
16     return 0;
17 }