当先锋百科网

首页 1 2 3 4 5 6 7

【HDU5742 2016 Multi-University Training Contest 2I】【简单讨论】It's All In The Mind 给定除法式尽量大

It's All In The Mind

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1138    Accepted Submission(s): 563

Problem Description
Professor Zhang has a number sequence   a_1,a_2,...,a_n. However, the sequence is not complete and some elements are missing. Fortunately, Professor Zhang remembers some properties of the sequence:

1. For every   i \in \{1,2,...,n\},   0 \le a_i \le 100.
2. The sequence is non-increasing, i.e.   a_1 \ge a_2 \ge ... \ge a_n.
3. The sum of all elements in the sequence is not zero.

Professor Zhang wants to know the maximum value of   \frac{a_1+a_2}{\sum_{i=1}^{n}{a_i}}  among all the possible sequences.
 

Input
There are multiple test cases. The first line of input contains an integer   T , indicating the number of test cases. For each test case:

The first contains two integers   n  and   m   (2 \le n \le 100, 0 \le m \le n)  -- the length of the sequence and the number of known elements.

In the next   m  lines, each contains two integers   x_i  and   y_i   (1 \le x_i \le n, 0 \le y_i \le 100, x_i < x_{i+1}, y_i \ge y_{i+1}) , indicating that   a_{x_i} = y_i .
 

Output
For each test case, output the answer as an irreducible fraction " p / q ", where   p ,   q  are integers,   q > 0 .
 

Sample Input 
  

   2
2 0
3 1
3 1
 

Sample Output 
  

   1/1
200/201
 

Author
zimpha
 

Source
2016 Multi-University Training Contest 2 


#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 105, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int a[N];
int gcd(int x, int y)
{
	return y == 0 ? x : gcd(y, x % y);
}
int main()
{
	int n, m;
	scanf("%d", &casenum);
	for (casei = 1; casei <= casenum; ++casei)
	{
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i)a[i] = 0;
		for (int i = 1; i <= m; ++i)
		{
			int x, y; scanf("%d%d", &x, &y);
			a[x] = y;
		}
		if (!a[1])a[1] = 100;
		if (!a[2])a[2] = a[1];
		a[n + 1] = 0; int top = a[1] + a[2]; int bot = top;
		for (int i = n; i >= 3; --i)
		{
			if (!a[i])a[i] = a[i + 1];
			bot += a[i];
		}
		int g = gcd(top, bot);
		printf("%d/%d\n", top/g, bot/g);
	}
	return 0;
}
/*
【trick&&吐槽】
这题我们是否要处理sum为0的情况？不需要，因为自然会规避。

【题意】
我们对不完整的数列a[]做填充。
使得——
1，a[]∈[0,100]
2，不上升
3，和非0
4，(a[1]+a[2])/sum尽可能大

【类型】
水题 讨论

【分析】
使得(a[1]+a[2])/sum尽可能大，也就是使得其倒数尽可能小。
也就是使得(a[3]+...+a[n])/(a[1]+a[2])尽可能小
所以显然——

1，我们要使得a[1]+a[2]尽可能大
2，我们要使得(a[3]+...+a[n])尽可能小（但是不能为负）

【时间复杂度&&优化】
O(n)

*/