参考大佬的博客写的很好https://blog.csdn.net/qq_43750980/article/details/103130387?ops_request_misc=%7B%22request%5Fid%22%3A%22160189465619724839206957%22%2C%22scm%22%3A%2220140713.130102334…%22%7D&request_id=160189465619724839206957&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v3~pc_rank_v2-3-103130387.first_rank_ecpm_v3_pc_rank_v2&utm_term=Gym±+102220B+&spm=1018.2118.3001.4187
题目
传送门
Input 2 2 1 2 7 1 2 1 3 2 1 2 2 1 5 2 3 2 Output 9/2 5/1
题意：首先给你一个数t，t组输入，然后两个数n，m分别表示糖的数量和种类，下面是m个数，分别表示m种类型糖你如果选它的话要至少选li个当然也可以不选它，再下面是n行，每行有两个数x，y，分别表示糖的甜度和糖的种类，现在要求S/C的最大值.S是你所选的糖的甜度和，C是你所选的某种类型糖的最大数量：例： 类型1 选5个糖 类型2 选7个糖 类型3 选4个糖 C=7
思路：先用一个vector存下每种糖的甜度，再用另一vector存下某种糖在你选最大数量为几时才可以选，直接暴力遍历你选某种糖的最大数量.
AC code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<sstream>
#include<stack>
#include<queue>
#include<vector>
using namespace std
;
#define ll long long
ll n
,t
,m
;
int a
[120000];
vector
<int>pp
[120000],o
[120000];
bool cmp(int x
,int y
)
{
return x
>y
;
}
void solve()
{
int x
,y
;
for(int i
=1;i
<=m
;i
++)cin
>>a
[i
];
for(int i
=0;i
<n
;i
++)
{
cin
>>x
>>y
;
pp
[y
].push_back(x
);
}
for(int i
=1;i
<=m
;i
++)
{
sort(pp
[i
].begin(),pp
[i
].end(),cmp
);
for(int j
=0;j
<pp
[i
].size();j
++)
{
o
[max(j
+1,a
[i
])].push_back(pp
[i
][j
]);
}
pp
[i
].clear();
}
ll x1
=0,x2
=0,y1
=1,y2
=0;
for(int i
=1;i
<=n
;i
++)
{
y2
=i
;
for(int j
=0;j
<o
[i
].size();j
++)
{
x2
+=o
[i
][j
];
}
if(x1
*y2
<x2
*y1
)
{
x1
=x2
;
y1
=y2
;
}
o
[i
].clear();
}
ll k
=__gcd(x1
,y1
);
printf("%lld/%lld\n",x1
/k
,y1
/k
);
}
int main()
{
ios
::sync_with_stdio(0);
cin
>>t
;
while(t
--)
{
cin
>>n
>>m
;
solve();
}
}
e自己大概写了一下过程，可能不是太清楚请大家见谅
