MYF

HDU 5127 Dogs' Candies

Posted on | In | | Visitors

题目链接

HDU 5127

题目类型：List的应用

题目分析

题目大意

Dog King有一个大盒子，最初的时候盒子是空的。盒子用于放糖，每个糖有一个甜度x和一个酸度y。每一条Dog对于甜度和酸度的热爱程度不一样，甜度的热爱程度为a，酸度的热爱程度为b，那么当前Dog对于一颗糖的总喜爱程度为a*x+b*y

Dog King有三种操作

  1. 向盒子里增加一个甜度为x，酸度为y的糖
  2. 从盒子中删除甜度为x，酸度为y的糖
  3. 查询。给出一条狗的甜度热爱度以及酸度热爱度，求狗对于盒子中的糖的最大总喜爱程度

解析

给了30s，看上去就很吓人，没想到最后竟然暴力就可以过，建立一个list，里面存储pair信息，每个pair表示一颗糖的酸度和甜度。直接调用STL的函数即可，看代码吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <list>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define fre() freopen("data_in.txt","r",stdin); \
			  freopen("data_out.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
const int maxn=100000+5;
list<pair<int, int> >v;
int main(){
	int n;
	while (scanf("%d",&n),n) {
		v.clear();
		while (n--) {
			int op,x,y;
			scanf("%d%d%d",&op,&x,&y);
			if (op == -1) 
				v.erase(find(v.begin(),v.end(),make_pair(x, y)));
			else if (op == 1) 
				v.push_back(make_pair(x, y));
			else {
				ll mx = -INF;
				for (list<PII>::iterator it = v.begin();it!=v.end();it++) 
					mx = max(mx, (ll)x*it->first+(ll)y*it->second);
				cout<<mx<<"\n";
			}
		}
	}
}