POJ-3484 Showstopper 题解

本文主要是介绍POJ-3484 Showstopper 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

POJ-3484 Showstopper

【二分-最大值最小化】

题目：
Data-mining huge data sets can be a painful and long lasting process if we are not aware of tiny patterns existing within those data sets.
One reputable company has recently discovered a tiny bug in their hardware video processing solution and they are trying to create software workaround. To achieve maximum performance they use their chips in pairs and all data objects in memory should have even number of references. Under certain circumstances this rule became violated and exactly one data object is referred by odd number of references. They are ready to launch product and this is the only showstopper they have. They need YOU to help them resolve this critical issue in most efficient way.
Can you help them?

输入：
Input file consists from multiple data sets separated by one or more empty lines.
Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.
Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of references: X, X+Z, X+2Z, X+3Z, …, X+KZ, …(while (X+KZ)<=Y).
Your task is to data-mine input data and for each set determine weather data were corrupted, which reference is occurring odd number of times, and count that reference.

输出：
For each input data set you should print to standard output new line of text with either “no corruption” (low case) or two integers separated by single space (first one is reference that occurs odd number of times and second one is count of that reference).

输入样例：
1 10 1
2 10 1

1 10 1
1 10 1

1 10 1
4 4 1
1 5 1
6 10 1

输出样例：
1 1
no corruption
4 3

题意：
给你多组数据，数据之间通过空行隔开。
对于每组数据，每行分别代表了X,Y,Z，同时代表数列Value=X+kZ(Value<=Y)
求出每组数据中，Value个数为奇数的Value和这个Value的个数。
例如样例：

1 10 1
4 4 1
1 5 1
6 10 1

根据每行的数列关系可以看作：

1 2 3 4 5 6 7 8 9 10
      4             
1 2 3 4 5           
          6 7 8 9 10

可以看到4有3(奇数)个。
所以样例答案为4 3。

题解：
本题的输入非常难写(先读字符串，再处理数据放入数组，利用空行判断是否读完数据)。
先获两个数值极限，l=0，r=最大值。
检查取最大值情况下，使用数值个数之和是否为偶数，如果是偶数，证明不会出现奇数个数值(因为如果存在则奇数个的数值只会有一种)，直接输出“no corruption”，并读取下一组数据，否则继续。
通过二分查找，检查当前二分结果Mid(利用等差数列性质求数值个数)，如果一共有偶数个数值，说明结果大于Mid，此时l=Mid+1。否则，证明Mid可能是答案，或者答案更小，继续收缩二分，即r=Mid。直到l>=r,此时r为逼近得到的答案。

AC代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
int n;
ll a[100005][3],m,l,r;
//读入数据 
void str_data(string &str){
	ll s=0;
	int i=0;
	for(i;i<str.size();i++){
		if(str[i]==' '){i++;break;}
		s*=10;
		s+=(str[i]-'0');
	}
	a[n][0]=s;
	s=0;
	for(i;i<str.size();i++){
		if(str[i]==' '){i++;break;}
		s*=10;
		s+=(str[i]-'0');
	}
	r=max(r,s);
	a[n][1]=s;
	s=0;
	for(i;i<str.size();i++){
		if(str[i]==' ')break;
		s*=10;
		s+=(str[i]-'0');
	}
	a[n][2]=s;
	n++;
}
ll cheak(ll mid){
	ll sum=0;
	for(int i=0;i<n;i++){
		if(a[i][1]>=a[i][0]&&mid>=a[i][0]){
			if(a[i][1]>mid){
				sum+=(mid-a[i][0])/a[i][2];	
			}
			else{
				sum+=(a[i][1]-a[i][0])/a[i][2];
			}
			sum++;
		}
	}
	return sum;
}
int main(){
	string str;
	while(getline(cin,str)){
		if(str=="")continue;
		n=0;l=0;r=0;
		str_data(str);
		while(getline(cin,str)){
			if(str=="")break;
			str_data(str);
		}
		if(cheak(r)%2==0){
			printf("no corruption\n");
			continue;
		}
		while(l<r){
			ll mid=(l+r)/2;
			if(cheak(mid)%2==1){
				r=mid;
			}
			else{
				l=mid+1;
			}
		}
		printf("%lld %lld\n",r, cheak(r)-cheak(r-1));
	}
}

这篇关于POJ-3484 Showstopper 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！