HLEP

WA求调

05-ZZ07-04-比比谁猜得准(1)

题目描述

在生活中，我们有时会玩“比谁猜得准”的游戏。比如，有3个人，A和B来猜一下这三个人的年龄总和，看谁猜得准。在本题中，我们把这个问题更一般化：给定n个正整数，A、B两个人来玩“比谁猜得准”的游戏，A和B各说一个数，比如a和b，看能否从这n各数中取若干个数（允许取0个数，即一个数都不选），使得这n个数的和越接近a或b越好（但不能超过）；比如从这n个数中取出若干数，这些数的和为m1，a-m1要大于或等于0，但这个差越小越好，设最小的差为d1；从这n个数中取出若干数，这些数的和为m2，b-m2要大于或等于0，但这个差越小越好，设最小的差为d2；如果d1<d2，则A赢了；如果d2<d1，则B赢了；如果d1=d2，则A和B打平了。

输入格式

输入文件第一行为两个正整数n和q，分别表示给定的数的个数，以及A和B玩游戏的次数，n≤100，q≤10000。第二行给出n个正整数，用空格隔开，这些数的范围是[1, 1000]。接下来有q行，每行有两个正整数a和b，分别表示A和B猜的数，a, b≤100000。

输出格式

对每次游戏，输出一行，因此总共输出q行。如果A赢了，输出A；如果B赢了，输出B；如果A和B打平了，输出tie。

样例 #1

样例输入 #1

10 3
264 138 931 978 956 669 91 453 402 1000
1691 1121
562 1352
2022 1195

样例输出 #1

A
B
tie

提示

样例说明：

第1次游戏，A猜的数字1691，最接近于931+669+91=1691，差距为0，B猜的数字1121，最接近于264+453+402=1119，差距为2，所以A赢；第2次游戏，A猜的数字562，最接近于91+453=544，差距为18，B猜的数字1352，最接近于138+669+91+453=1351，差距为1，所以B赢；第3次游戏，2022=931+91+1000，1195=264+931，A和B都猜得很准，2个差d1和d2均为0，所以打平了。

---

WA代码↓

#include<bits/stdc++.h>
using namespace std;
int a[110];
int f[110][100010];
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int j=1;j<=n;j++){
		if(a[n]<=100010){
			f[n][j]=a[n];
		}
	}
	for(int i=n-1;i>=1;i--){
		for(int j=1;j<=100010;j++){
			if(a[i]>j){
				f[i][j]=f[i+1][j];
			}else{
				f[i][j]=max(f[i+1][j],f[i+1][j-a[i]]+a[i]);
			}
			
		}
	}
	int a,b,m1,m2,d1,d2;
	for(int i=1;i<=q;i++){
		cin>>a>>b;
		m1=f[1][a],m2=f[1][b];
		d1=a-m1,d2=b-m2;
		if(d2>d1){
			cout<<"A"<<endl;
		}else if(d1>d2){
			cout<<"B"<<endl;
		}else{
			cout<<"tie";
		}
	}
	return 0;
}