Northeast Collegiate Programming Contest"/>
The 13th Chinese Northeast Collegiate Programming Contest
文章目录
- B. Balanced Diet
- C. Line-line Intersection
- E. Minimum Spanning Tree
- D. Master of Data Structure
- F. Mini-game Before Contest 坑
- G. Radar Scanner
- H. Skyscraper
- J. Time Limit
链接
B. Balanced Diet
贪心,假设最大天数为k,那么所有物品最大得k项都拿(再满足题意的情况下)
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+9;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
//LL __gcd(LL x,LL y){return y==0?x:__gcd(y,x%y);}
//head
int n,_,p[maxn],m,mx;
LL s[maxn];
VI G[maxn];
int main(){scanf("%d",&_);while(_--){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d",&p[i]);G[i].clear();}for(int i=1,x,y;i<=n;i++){scanf("%d%d",&x,&y);G[y].pb(x);}for(int i=1;i<=m;i++){sort(G[i].begin(),G[i].end());reverse(G[i].begin(),G[i].end());}for(int i=1;i<=m;i++){LL sum=0;for(int j=0;j<G[i].size();j++){s[max(j+1,p[i])]+=G[i][j];//printf("%llds",sum);}}LL zi=0,mu=1;for(int i=1;i<=n;i++) s[i]+=s[i-1];for(LL i=1;i<=n;i++){if(zi*i<s[i]*mu) zi=s[i],mu=i;//printf("%lld",s[i]);s[i]=0;}LL gcd=__gcd(zi,mu);printf("%lld/%lld\n",zi/gcd,mu/gcd);}
}
C. Line-line Intersection
两条直线有交点即斜率不同,用mp模拟就好(脑子抽抽,错了十几次
更多推荐
The 13th Chinese Northeast Collegiate Programming Contest
发布评论