题解 | TheGrandFarm-off-牛客假日团队赛
The Grand Farm-off
https://ac.nowcoder.com/acm/contest/1081/H
题目描述
Farmer John ownsThis competition allows him to enter a group of N cows. He has given each of his cows a utility rating
There might be multiple sets of N cows that attain the maximum utility sum. FJ is afraid the competition may impose a total weight limit on the cows in the competition, so a secondary priority is to bring lighter weight competition cows.
Help FJ find a set of N cows with minimum possible total weight among the sets of N cows that maximize the utility, and print the remainder when this total weight is divided by
Note: to make the input phase faster, FJ has derived polynomials which will generate the weights and utility values for each cow. For each cowmod d and
mod h with reasonable ranges for the coefficients (
). The formulae do sometimes generate duplicate numbers; your algorithm should handle this properly.
输入描述:
* Line 1: Ten space-separated integers: N, a, b, c, d, e, f, g, h, and M
输出描述:
* Line 1: A single integer representing the lowest sum of the weights of the N cows with the highest net utility.
示例1
输入
2 0 1 5 55555555 0 1 0 55555555 55555555
输出
51
说明
The functions generate weights of 5, 6, 9, 14, 21, and 30 along with utilities of 0, 1, 8, 27, 64, and 125.
The two cows with the highest utility are cow 5 and 6, and their combined weight is 21+30=51.
解答
很简单，按照题意算一遍
排序，优先u，再排w
u降序，w升序
前n个一定最优
算时一定要从0下标开始
排序，优先u，再排w
u降序，w升序
前n个一定最优
算时一定要从0下标开始
#include <cstdio>
#include <algorithm>
using namespace std;
struct P{
int w,u;
friend bool operator <(P p,P q){
if(p.u==q.u){
return p.w<q.w;
}
return p.u>q.u;
}
}array[3*500000+5];
int main(){
int n,a,b,c,d,e,f,g,h,m;
scanf("%d%d%d%d%d%d%d%d%d%d",&n,&a,&b,&c,&d,&e,&f,&g,&h,&m);
long long i2,i3,i5;
for(long long i=0;i<3*n;i++){//零下标
i2=(i*i)%d;
i3=(i2*i)%d;
i5=((i3*i)%d*i)%d;
array[i+1].w=((a*i5)%d+(b*i2)%d+c%d)%d;
i2=(i*i)%h;
i3=(i2*i)%h;
i5=((i3*i)%h*i)%h;
array[i+1].u=((e*i5)%h+(f*i3)%h+g)%h;
}
sort(array+1,array+1+3*n);
long long ans=0;
for(int i=1;i<=n;i++){
ans+=array[i].w;
ans%=m;
}
printf("%lld\n",ans);
return 0;
} 其实这题主要是题意理解，还有，要用long long 来源：2016wudi
投递淘天集团等公司10个岗位 >
