PKUoj–An Easy Task

作者:luozhipeng   发表日期:2015-4-30  浏览:1,066次

C14B:An Easy Task

总时间限制:
1000ms
内存限制:
65536kB
描述
You are given an easy task by your supervisor -- to find the best value of X, one of the parameters in an evaluation function, in order to improve the accuracy of the whole program.However, after a few days' analysis, you realize that it is far harder than you imagine. There are so many values X can be, and the only way to find the best one among them is to try all these possible values one after another!Fortunately, you know that X is an integer and thanks to the previous works by your senior fellow apprentices, you have got n constraints on X. Each constraint must be in one of the following forms:
1. < k: means that X is less than integer k;
2. > k: means that X is greater than integer k;
3. <= k: means that X is less than or equal to integer k;
4. >= k: means that X is greater than or equal to integer k;
5. = k: means that X is equal to integer k.Now, you are going to figure out how many possible values X can be, so that you can estimate whether it is possible to finish your task before deadline.

输入
The first line contains an integer T (1 ≤ T ≤ 10) -- the number of test cases.For each test case:
The first line contains an integer n. 0 ≤ n ≤ 10 000.
Then follows n lines, each line contains a comparison operator o and an integer k, separated by a single space. o can be one of “>”, “<”, “>=”, “<=”, and “=”. 0 ≤ | k | ≤ 1 000 000 000.
There is no contradictory between these constraints, in other word, at least one integer value meets all of them.
输出
For each test case, output one integer in a single line -- the number of possible values of X, or “-1” if the answer is infinite.
样例输入
1
2
> 2
<= 5
样例输出
3
#include <iostream>
#include <stdio.h>
#include <string>
#define inf 1000000001
using namespace std;
int main()
{
    int T,n;
    int a,b,x;
    string str;
    cin>>T;
    while(T--) {
       cin>>n;
       a = -inf;
       b = inf;
       while(n--) {
          cin>>str>>x;
          if(str == ">") {
             if(x +1 > a)
                 a = x+1;
          }
          else if(str == ">=") {
             if(x > a)
                 a = x;
          }
          else if(str == "<") {
              if(x - 1 < b)
                 b = x-1;
          }
          else if(str == "<="){
              if(x < b)
                 b = x;
          }
          else{ //"="
             if(x >= a && x <=b){
                 a = x;
                 b = x;
             }
             else
                 a = b + 1;
         }
      }
      if(a == -inf || b == inf || b - a < 0)
         cout<<-1<<endl;
      else
         cout<<b -a +1 <<endl;
    }
 return 0;
}

本文固定链接: http://www.luozhipeng.com/?p=125
转载请注明: luozhipeng 2015-4-30 于 罗志鹏的BLOG 发表

上一篇: :下一篇
评论:请安装多说插件!
返回顶部