首页 > 代码库 > uva1588kickdown

uva1588kickdown

题目要求简述:给定长度分别为n1,n2(n1,n2<=100)且每列的高度只为1或者2的长条。需要将他们放入一个高度为3的容器,问能够容纳它们的最短容器长度。

思路就是固定一个字符串a,字符串b移动,再固定b,让a移动,取二者长度最小值。

之前写的函数有问题,wrong answer错误了很多遍,调试的时候学习了重定向,参考了一篇博客ac的。

#include<fstream> 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define max 110
using namespace std;

int min(const int &i, const int &j) {
    return i<j ? i : j;
}

int offset(char *s1, char *s2, int &ls1, int &ls2) {
    int sum = ls1 + ls2, f, l = ls1 + ls2, minn = min(ls1, ls2);
    bool flag;
    for (int i = 0;i < ls1;i++) {
        flag = true;f = min(minn, ls1 - i);
        for (int j = 0;j < f;j++) {
            if ((s1[i + j] == 2) && (s2[j] == 2)) {
                flag = false;
                break;
            }
        }
        if (flag&&l > sum - f) {
            l = sum - f;
        }
    }
    return l;
}

int main()
{
    int offset(char *s1, char *s2, int &ls1, int &ls2);
    char str1[max],str2[max];
    int l1,l2;
    /*ifstream fin("G:\\algorithm\\uva\\input\\1588in.txt"); 
    ofstream fout("G:\\algorithm\\uva\\output\\result.txt"); 
    streambuf *cinbackup;
    streambuf *coutbackup;
    coutbackup = cout.rdbuf(fout.rdbuf());
    cinbackup = cin.rdbuf(fin.rdbuf()); */
    while (cin >> str1 >> str2) {
        l1 = strlen(str1);
        l2 = strlen(str2);
        int res1 = offset(str1,str2,l1,l2);
        int res2 = offset(str2,str1,l2,l1);
        cout << min(res1,res2) << endl;
        memset(str1, 0, sizeof(str1));
        memset(str2, 0, sizeof(str2));
    }
    return 0;
}

参考博客地址

uva1588kickdown