uva 10700 - Camel trading

点击打开链接

题目意思：     给定一个表达式，要求找到这个表达式的最大值和最小值

解题思路：     1:思路：模拟题
                      2：对于给定的一个表达式，最小值就是直接去计算这个表达式。如果要求算出的值最大，那么我们知道乘号的个数是不会改变的，所以如果能够让乘号旁边的数字越大越好，所 以我们把所有+旁边的数全部加为一个数，然后在计算就是最大值，例如3+11+4*1*13*12*8+3*3+8应该就是要（3+11+4）*（1）*（13）*（12）*（8+3）*（3+8）
                      3:由于这里的数字是1-20，并且最多有12个，那么最坏情况20*20.........*20,20个连乘那么结果超过int，所以用long long才保证正确，这个地方WA了N次，后来含着泪A了
                      4:这一题用到了两个常用于处理字符串，1 split函数用来切割字符串 2 sscanf用来读取字符串中的数字.见我博客《ACM---资料收集》有详细的介绍

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 100

int t;
long long  s[MAXN];
char ch[50];

void solve(){
    long long  min , max;//longlong
    long long i , j , tmp , a;
    char str[MAXN][100] , tmp_ch[MAXN];
    memset(s , 0 , sizeof(s));

    //求最小值
    memcpy(tmp_ch , ch , sizeof(tmp_ch));
    const char *split = "+" ; char *p;
    p = strtok(tmp_ch , split) ; i = 0;
    while(p != NULL){
        strcpy(str[i++] , p);
        p = strtok(NULL,split);
    }
    for(j = 0 , min = 0; j < i ; j++){
        split = "*" ; tmp = 1;
        p = strtok(str[j] , split);
        while(p != NULL){
            sscanf(p , "%lld" , &a) ; tmp *= a;
            p = strtok(NULL, split);
        }
        min += tmp;
    }

    //求最大值
    memcpy(tmp_ch , ch , sizeof(tmp_ch));
    memset(s , 0 , sizeof(s));
    split = "*" ;
    p = strtok(tmp_ch,split) ; i = 0;
    while(p != NULL){
        strcpy(str[i++] , p) ; p = strtok(NULL,split);
    }
    for(j = 0 ; j < i ; j++){
        split = "+" ; tmp = 0;
        p = strtok(str[j] , split);
        while(p != NULL){
            sscanf(p , "%lld" , &a) ; tmp += a;
            p = strtok(NULL, split);
        }
        s[j] = tmp;
    }
    for(i = 0 , max = 1 ; s[i] != 0 ; i++) max *= s[i];
    printf("The maximum and minimum are %lld and %lld.\n" , max , min);
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    scanf("%d%*c" , &t);
    while(t--){
         gets(ch) ; solve();
    }
    return 0;
}