POJ3617

Best Cow Line

题意

给定长度为N的字符串S，要构造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下列任意操作：

从S的头部（或尾部）删除一个字符，加到T的尾部

目标是构造字典序尽可能小的字符串T。

思路

贪心算法，不断取S的开头和末尾中较小的一个字符放到T的末尾。但对于S的开头和末尾字符相同的情况下，需要比较下一个字符大小，这可以用如下算法实现：

按照字典序比较S和S翻转后的字符串S1，如果S较小，则从S的开头取，否则从末尾取。

代码

Source Code

Problem: 3617       User: liangrx06

Memory: 728K        Time: 47MS

Language: G++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

#define N 2000

int main(void)

{

    int n, i, j, k, ii, jj;

    char s[N+1], t[N+1];

    while (cin >> n)

    {

        for (i=0; i<n; i++) {

            getchar();

            scanf("%c", &s[i]);

        }

        s[i] = '\0';

        i = 0;

        j = n-1;

        k = 0;

        while (i <= j) {

            ii = i, jj = j;

            while (ii <= jj) {

                if (s[ii] != s[jj])

                    break;

                ii ++;

                jj --;

            }

            if (ii <= jj && s[ii] > s[jj]) {

                t[k++] = s[j];

                j --;

            }

            else {

                t[k++] = s[i];

                i ++;

            }

        }

        t[k] = '\0';

        for (i = 0; i < n; i++)

        {

            printf("%c", t[i]);

            if (i % 80 == 79) printf("\n");

        }

        if (n % 80) printf("\n");

    }

    return 0;

}

POJ3069

Saruman’s Army

题意

这个题是说给你n个点，然后让你标记其中尽可能少的点，使得n个点都处于被标记点左右不超过R的区间内。

思路

贪心法求解，从左到右选择。

代码

Source Code

Problem: 3069       User: liangrx06

Memory: 748K        Time: 125MS

Language: G++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

#define N 1000

int main(void)

{

    int r, n, i, j;

    int pos[N], res;

    while (cin >> r >> n) {

        if (r == -1 && n == -1)

            break;

        for (i=0; i<n; i++)

            cin >> pos[i];

        sort(pos, pos+n);

        res = 0;

        i = 0;

        while (i < n) {

            j = i+1;

            while (j < n && pos[j] - pos[i] <= r)

                j ++;

            j --;

            i = j+1;

            while (i < n && pos[i] - pos[j] <= r)

                i ++;

            res ++;

        }

        cout << res << endl;

    }

    return 0;

}

POJ3253

Fence Repair

题意

有一个农夫要把一个木板钜成几块给定长度的小木板，每次锯都要收取一定费用，这个费用就是当前锯的这个木版的长度。给定各个要求的小木板的长度，及小木板的个数n，求最小费用。

提示：

以

3

5 8 5

为例：

先从无限长的木板上锯下长度为 21 的木板，花费 21

再从长度为21的木板上锯下长度为5的木板，花费5

再从长度为16的木板上锯下长度为8的木板，花费8

总花费 = 21+5+8 =34

思路

利用Huffman思想，要使总费用最小，那么每次只选取最小长度的两块木板相加，再把这些“和”累加到总费用中即可

本题虽然利用了Huffman思想，但是直接用HuffmanTree做会超时，可以用优先队列做

代码

Source Code

Problem: 3253       User: liangrx06

Memory: 1184K       Time: 219MS

Language: C++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <set>

using namespace std;

int main(void)

{

    int n, i;

    long long x, sum;

    multiset <long long> plank;

    while (cin >> n)

    {

        for (i=0; i<n; i++) {

            cin >> x;

            plank.insert(x);

        }

        sum = 0;

        while (plank.size() > 1)

        {

            x = *(plank.begin()) + *(++plank.begin());

            sum += x;

            plank.erase(plank.begin());

            plank.erase(plank.begin());

            plank.insert(x);

        }

        cout << sum << endl;

        plank.clear();

    }

    return 0;

}

POJ2393

Yogurt factory

题意

有n周，第i周：需要向外供货yi，生产1单位成本ci。若非本周生产的货物不在本周销售，需要贮藏，1单位贮藏一周需要花费s。问n周供货供需花费多少钱（成本和贮藏费）。

思路

贪心，我们用minc记录当前的最小单价，然后以最小单价买入，这个最小单价，要么是现在的单价，要么是之前的最小单价＋贮藏费。minc中被替换掉的值是不可能是以后的最小单价的。因为现在被替换，同时＋上若干个s之后它还是会比现在替换它的那个值大。

代码

Source Code

Problem: 2393       User: liangrx06

Memory: 132K        Time: 16MS

Language: C++       Result: Accepted

Source Code

#include<iostream>

using namespace std;

int main()

{

    int n, s, minc = 9999;

    scanf("%d %d", &n, &s);

    long long sum = 0;

    while(n --){

        int c, y;

        scanf("%d %d", &c, &y);

        if(c > minc + s)

            c = minc + s;

        minc = c;

        sum += c * y;

    }

    printf("%lld\n", sum);

    return 0;

}

POJ1017

Packets

题意

问题描述

一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个

型号，他们的长宽分别为 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. 这些产品通常使用一个 6*6*h

的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的

包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由

你来设计。

输入数据

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空

格隔开，分别为 1*1 至6*6 这六种产品的数量。输入文件将以 6 个0 组成的一行结尾。

输出要求

除了输入的最后一行6 个0 以外，输入文件里每一行对应着输出文件的一行，每一行输

出一个整数代表对应的订单所需的最小包裹数。

输入样例

0 0 4 0 0 1

7 5 1 0 0 0

0 0 0 0 0 0

输出样例

2

1

思路

这个问题描述得比较清楚，我们在这里只解释一下输入输出样例：共有两组有效输入， 第一组表示有4 个3*3 的产品和一个6*6 的产品，此时4 个 3*3 的产品占用一个箱子，另外 一个 6*6 的产品占用 1 个箱子，所以箱子数是 2；第二组表示有7 个 1*1 的产品，5 个 2*2 的产品和1 个 3*3 的产品，我们可以把他们统统放在一个箱子中，所以输出是1。

分析六个型号的产品占用箱子的具体情况如下：6*6的产品每个会占用一个完整的箱 子，并且没有空余空间；5*5 的产品每个占用一个新的箱子，并且留下 11 个可以盛放 1*1 的产品的空余空间；4*4 的产品每个占用一个新的箱子，并且留下5 个可以盛放2*2 的产品 的空余空间；3*3 的产品情况比较复杂，首先3*3 的产品不能放在原来盛有5*5 或者4*4 的箱子中，那么必须为3*3 的产品另开新的箱子，新开的箱子数目等于3*3 的产品的数目除以 4 向上取整；同时我们需要讨论为3*3 的产品新开箱子时，剩余的空间可以盛放多少2*2 和 1*1 的产品（这里如果有空间可以盛放2*2 的产品，我们就将它计入2*2 的空余空间，等到 2*2 的产品全部装完，如果还有2*2 的空间剩余，再将它们转换成 1*1 的剩余空间）。我们 可以分情况讨论为3*3 的产品打开的新箱子中剩余的空位，共为四种情况：第一种，3*3 的 产品的数目正好是4 的倍数，所以没有空余空间；第二种，3*3 的产品数目是4 的倍数加1， 这时还剩 5 个2*2 的空位和7 个 1*1 的空位；第三种，3*3 的产品数目是4 的倍数加2，这时还剩3 个2*2 的空位和6 个 1*1 的空位；第四种，3*3 的产品数目是4的倍数加3，这时 还剩 1 个 2*2 的空位和5 个 1*1 的空位；处理完3*3 的产品，就可以比较一下剩余的2*2 的空位和2*2 产品的数目，如果产品数目多，就将2*2 的空位全部填满，再为2*2 的产品打开新箱子，同时计算新箱子中 1*1 的空位，如果剩余空位多，就将2*2 的产品全部填入2*2的空位，再将剩余的 2*2 的空位转换成 1*1 的空位；最后处理 1*1 的产品，比较一下 1*1的空位与1*1 的产品数目，如果空位多，将1*1 的产品全部填入空位，否则，先将1*1 的空位填满，然后再为 1*1 的产品打开新的箱子。

代码

Source Code

Problem: 1017       User: liangrx06

Memory: 132K        Time: 16MS

Language: C++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

bool input(int a[])

{

    bool flag = false;

    for (int i = 1; i <= 6; i ++) {

        scanf("%d", &a[i]);

        if (a[i] != 0) flag = true;

    }

    return flag;

}

int main(void)

{

    int a[7];

    int i, k, m, res;

    while (input(a)) {

        res = 0;

        for (i = 6; i >= 1; i --) {

            k = (6/i)*(6/i);//每个包裹能放的第i个产品的数量

            m = a[i]/k;//需要的包裹数量

            a[i] %= k;

            int n1 = 6*6*m - i*i*m*k;//剩下多少个1*1

            if (a[i]) n1 += 6*6 - i*i*a[i];

            if (i == 3 || i == 4) {

                int n2 = 0;//剩下多少个2*2

                if (i == 4)

                    n2 += 5*m;

                else if (i == 3 && a[i])

                    n2 += (4-a[i])*2 - 1;

                if (n2 > a[2])

                    n2 = a[2];

                a[2] -= n2;

                //printf("n1=%d, n2=%d\n", n1, n2);

                n1 -= 2*2*n2;

                //printf("n1=%d, n2=%d\n", n1, n2);

            }

            if ( i >= 2 && i <= 5 ) {

                if (n1 > a[1])

                    n1 = a[1];

                a[1] -= n1;

            }

            //for (int x = 1; x <= 6; x ++)

            //  printf("%d ", a[x]);

            //printf("\n");

            res += m;

            if (a[i])

                res ++;

            a[i] = 0;

        }

        printf("%d\n", res);

    }

    return 0;

}

POJ3040

Allowance

题意

有N种不同面额的纸币，你雇佣的一个人，每次支付至少C圆。每种纸币的面额大小为V（每种纸币的大小成整倍数关系这是结题的关键），张数为B，问你最多能支付多少次？

思路

将V从小到大进行一个排列

1.先把大于C元的纸币用了，进行一个计数

2.再从大的纸币进行抓取，抓得越多越好，但要小于等于C，如果等于C进行一个计数，如果小于C，再将纸币从小的抓取，大于C进行一个计数。因为纸币是成倍数关系的，你最大的纸币面额，比前面所有纸币面额加起来都大。

3.最后进行一个支付情况的总加，意思是，你后面还能像这第2步这样支付方案的个数，然后再从第2步开始，直到不能支付。

代码

Source Code

Problem: 3040       User: liangrx06

Memory: 212K        Time: 16MS

Language: C++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 20;

struct Coin {

    int v, b;

};

bool cmp(const Coin &x, const Coin &y)

{

    return x.v < y.v;

}

int n, c;

int m[N];

Coin coin[N];

int sum;

bool choose(int i)

{

    m[i] = sum / coin[i].v;

    if (m[i] > coin[i].b)

        m[i] = coin[i].b;

    sum -= m[i]*coin[i].v;

    if (sum == 0)

        return true;

    if (i == 0 || choose(i-1) == false) {

        if (coin[i].b > m[i]) {

            sum -= coin[i].v;

            m[i] ++;

            return (sum <= 0);

        }

        return false;

    }

    return true;

}

bool canPay()

{

    memset(m, 0, sizeof(m));

    sum = c;

    return choose(n-1);

}

int main(void)

{

    int i;

    cin >> n >> c;

    for (i = 0; i < n; i ++)

        cin >> coin[i].v >> coin[i].b;

    sort(coin, coin+n, cmp);

    int res = 0;

    while (canPay()) {

        int k = (int)1e9;

        //for (i = 0; i < n; i ++)

        //  printf("%d ", m[i]);

        //printf("\n");

        for (i = 0; i < n; i ++) {

            if (m[i] > 0) {

                int t = coin[i].b / m[i];

                k = (t < k) ? t : k;

            }

        }

        for (i = 0; i < n; i ++) {

            if (m[i] > 0) {

                coin[i].b -= m[i] * k;

            }

        }

        res += k;

        //break;

    }

    printf("%d\n", res);

    return 0;

}

POJ1862

Stripies

题意

科学家发现一种奇怪的玩意，他们有重量weight，如果他们碰在一起，总重变成2*sqrt(m1*m2)。要求出最终的重量的最小值。

思路

试一下就可以发现：对重量较大的先碰，可以对其多次sqrt，使得最后的结果最小。

代码

Source Code

Problem: 1862       User: liangrx06

Memory: 220K        Time: 16MS

Language: C++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int N = 10000;

int n;

double a[N];

void input()

{

    cin >> n;

    for (int i = 0; i < n; i ++) {

        cin >> a[i];

    }

}

double coll(double x, double y)

{

    return 2*sqrt(x*y);

}

double solve()

{

    sort(a, a+n);

    for (int i = n-2; i >= 0; i --)

        a[i] = coll(a[i], a[i+1]);

    return a[0];

}

int main(void)

{

    input();

    double res = solve();

    printf("%.3lf\n", res);

    return 0;

}

POJ3262

Protecting the Flowers

题意

有n个牛在FJ的花园乱吃。

所以FJ要赶他们回牛棚。

每个牛在被赶走之前每秒吃Di个花朵。赶它回去FJ来回要花的总时间是Ti×2。在被赶走的过程中，被赶走的牛就不能乱吃。

思路

贪心策略，对牛进行排序，排序的标准是，假设牛A与牛B要选一头赶走，我们首先要选择破坏最大的一头牛赶走，留破坏小的牛。他们的破坏着呢麽计算呢？假设先赶走牛A，那么牛B造成的损失是2×TA×DB，先赶走牛B，那么牛A造成的损失是2×TA×DB，所以，只要判断TA×DB与TA×DB谁大，就知道该先赶走谁了，所以数组排序的标准就是—Ti×Dj>Tj×Di。

代码

Source Code

Problem: 3262       User: liangrx06

Memory: 1780K       Time: 141MS

Language: C++       Result: Accepted

Source Code

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 100000;

struct Cow {

    int t, d;

    double v;

};

int n;

Cow cow[N];

void input()

{

    cin >> n;

    for (int i = 0; i < n; i ++) {

        scanf("%d%d", &cow[i].t, &cow[i].d);

        cow[i].v = (double)(cow[i].d)/(double)(cow[i].t);

    }

}

bool cmp(const Cow &x, const Cow &y)

{

    return x.v > y.v;

}

void solve()

{

    sort(cow, cow+n, cmp);

    long long res = 0;

    int time = 0;

    res += time * cow[0].d;

    for (int i = 1; i < n; i ++) {

        time += 2*cow[i-1].t;

        res += time * cow[i].d;

    }

    printf("%lld\n", res);

}

int main(void)

{

    input();

    solve();

    return 0;

}

最新文章

  1. Spring学习记录1--@Transactional Propagation
  2. linux 项目环境搭建配置
  3. java--实现将文字生成二维码图片，并在中间附上logo，下方附上文字
  4. django inclusion_tag
  5. sencha touch之模型(model)
  6. cuda-convnet 卷积神经网络 一般性结构卷积核个数 和 输入输出的关系以及输入输出的个数的说明:
  7. elfiner-servlet 2.x已开源！
  8. JQuery jsonp使用小记
  9. 接口测试:如何定位BUG的产生原因
  10. ZUFEOJ 2395 天棋哥哥大战AlphGo
  11. Linux常用命令List
  12. php生成器使用总结
  13. javascript 之异常处理try catch finally--05
  14. Python一个命令开启http下载服务器（可以局域网内共享文件）
  15. Erlang 集群互连测试
  16. UI分层中使用PageFactory
  17. linq中分组查询而且获取每个分组中的第一条记录，数据用于分页绑定
  18. mysql快熟入门
  19. 关于Sentry（转）
  20. HTTP方法之GET与POST对比

热门文章

  1. MDK5.00中*** error 65: access violation at 0xFFFFFFFC : no &#39;write&#39; permission的一种解决方法
  2. python3 logging 日志记录模块
  3. 0xffff0000颜色表示
  4. mapper.xml文件
  5. atitit.LimeSurvey 安装 attilax 总结
  6. C# asp.net页面常用语法,页面包含
  7. makefile之目录搜索＆自动依赖
  8. JS高程3：事件
  9. 【积累】javascript tips代码段
  10. ES查看配置和查看全部配置