Practice_17_01_ABC

A_Puzzles

　　共有m件拼图玩具，每件玩具拼图碎片数量不等，要求购买n件拼图，并且n件拼图中拼图碎片数量差值的最大值尽可能的小。

　　输入

　　　　n  m (2<=n<=m<=50)

　　　　f1 f2 ... fm (4<=fi<=1000)

　　输出

　　　　可得到的最小差值（int）

思路　　对拼图碎片数量进行排序，得到新的递增的数组，取第i个值和第i+n-1个值(0<=i<=m-n)得到两者之差ti，ti的最小值即为所要输出的最小差值。

AC代码：

#include <iostream>
 
 using namespace std;
 
 int main()
 {
         int n,m,f[50];
         int t,i,j,x,T;
 
         cin>>n>>m;
         for(i=0;i<m;i++){
             cin>>f[i];
         }
         for(i=0;i<m;i++){
             for(j=i+1;j<m;j++){
                 if(f[i]>f[j]){
                     x=f[i];
                     f[i]=f[j];
                     f[j]=x;
                 }
             }
         }
         for(i=0;i<m-n+1;i++){
             t=f[i+n-1]-f[i];
             if(T>t)
                 T=t;
         }
         cout<<T<<endl;
 }

 

 B_Dragon of Loowate

To slay the dragon, we must chop off all its heads. Each knight can chopoff one of the dragon's heads. The heads of the dragon are of different sizes. In order to chop off a head, a knight must be at least as tall as the diameter of the head. The knights' union demands that for chopping off a head, a knight must be paid a wage equal to one gold coin for each centimetre of the knight's height.The king wanted to minimize the expense of slaying the dragon.

　　输入

　　　　多组数据，第一行为龙的头的数量n，骑士数量m（1<=n,m<=20000)；接下来的n行均为一　　　　

　　个整数表示每个龙头的直径，下面的m行整数表示每个骑士的身高。

　　　　最后一个测试用例为‘0 0’。

　　输出

　　　　如果能够杀死龙，输出需要支付的最小费用

　　　　如果不能杀死龙，输出`Loowater is doomed!'。

思路　　首先处理n>m的情况，然后分别对龙头直径和骑士身高进行排序，得到两个递增数列，然后从小到大进行比对并记录所需金币数量，若遇到某个龙头不存在比其直径大的骑士身高时不能杀死龙，若比对到最后一个龙头依旧存在比直径大的骑士身高，则输出最小费用，即满足条件的骑士组合的最小身高和。（在这里排序的时候我下意识的使用了冒泡结果超时了〒▽〒后来改成了用algorithm库中的sort()函数

sort(begin,end);    //将[begin,end]区间上的数按升序排列，该函数在通常情况下使用快速排序

AC代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n,m,d[20000],h[20000],g;
    int i,j,t;

    while(true){
        cin>>n>>m;
        if(n==0||m==0)
            break;
        for(i=0;i<n;i++)
            cin>>d[i];
        for(i=0;i<m;i++)
            cin>>h[i];
        if(n>m){
            cout<<"Loowater is doomed!"<<endl;
            continue;
        }
        sort(d,d+n);
        sort(h,h+m);
        j=0;
        g=0;
        for(i=0;i<m;i++){
            if(h[i]>=d[j]){
                g=g+h[i];
                ++j;
                if(j==n)
                break;
            }
        }
        if(j<n)
            cout<<"Loowater is doomed!"<<endl;
        else
            cout<<g<<endl;
    }
    return 0;
}

 

C_Copying Books

　　m本书，k个抄写员，将m本书组成的序列分成k个顺序子序列，要求每个序列不为空。求在该划分方式下，最大子序列和最小的划分。

　　输入

　　　　n个案例，第一行为正整数n，每个案例由两行组成

　　　　第一行为书本数m和抄写员人数k(1<=k<=m<=500)

　　　　第二行有m个整数为每本书的页数pi(0<=pi<=10000000)

　　输出

　　　　序列pi的划分，由“/”分隔，且任意数字间、数字与“/”间均有一个空格字符。

思路　　采用二分法求满足约束条件的耗时最小的划分，具体模型如下：

　　以总页数即∑pi为上界，单本书最大页数max(p1...pi)为下界求得中间值进行二分求解，并在每个中项下，从右往左贪心，以此得到逼近题解条件的上界。若此时得到的分组数为k则直接按标记的分组输出，若分组数不足k则把前面（左端）分组拆分。

WA代码：（该代码少量数据结果正确，但大量数据时所分的小组数有问题o(╥﹏╥)o

#include <iostream>
#include <string.h>

using namespace std;

int m,p[500];
int num;
int sign[500];

int qrouping(int x){        //分组_贪心
    int sum=0,i;
    num=1;
    memset(sign,0,500);
    for(i=m-1;i>=0;i--){
        sum=sum+p[i];
        if(sum>x){
            ++num;
            sum=p[i];
            sign[i]=1;
        }
    }
    return num;
}
int main(){
    int n,k,sum,p_max;
    int i,mid;

    cin>>n;
    while(n--){
        cin>>m>>k;
        sum=p_max=0;
        for(i=0;i<m;i++){
            cin>>p[i];
            sum=sum+p[i];
            if(p[i]>p_max)
                p_max=p[i];
        }
        while(p_max<sum){
            mid=(p_max+sum)/2;
            if(qrouping(mid)<=k)
                sum=mid;
            else p_max=mid+1;     //不能直接跳出...直接跳出标记值不对...
        }
        num=qrouping(sum);

        for(i=0;i<m&&num<k;i++){
            if(sign[i]==0){
                sign[i]=1;
                ++num;
            }
        }
        cout<<p[0];
        for(i=1;i<m;i++){
            if(sign[i-1])
                cout<<" /";
            cout<<' '<<p[i];
        }
        cout<<endl;
    }

    return 0;
}