【noip模拟赛4】汽艇模拟

描述

一天sxc,zsx,wl到gly坐汽艇，本来和其他的人约好了一起去,结果被放了鸽子，3人便只有一人负担x元去坐汽艇(很贵哦)。坐了才发现如果汽艇上人多了位置就不宽敞，就不好玩了。而3个人貌似是最好玩的,但究竟是不是呢？假设有n个人要去坐1个汽艇，每个人单独坐汽艇的快乐程度是Ci，每多一个人，他的快乐程度会减去Di，请求出使快乐程度之和达到最大的方案。（假设汽艇的容量足够大）。

输入

输入文件共有3行：

第1行是一个整数n；

第2行有n个整数，依次表示每个人单独坐汽艇的快乐程度Ci（1<=Ci<=10000）；

第3行有n个整数，依次表示每多1人，每个人快乐程度的下降值Di（1<=Di<=10）。

输出

应输出两行：

第1行一个整数，是最大的快乐程度之和；

第2行一个整数，是最大的快乐程度之和所对应的汽艇上的人数（若有多种方案，则输出人数最多的）。

输入样例 1

6

10 10 10 10 10 9

2 2 2 2 2 3

输出样例 1

18

3

一看很像贪心算法 和背包有关  但是价值一直在改变
因为  价值为  c-nd   所以可以枚举n
此时所有人的价值是固定的  再排序取前n个人 

只要一一枚举n即可
比较巧妙的模拟

#include<bits/stdc++.h>

using namespace std;

//input

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m);

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s);

#define LL long long

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

#define N 15

struct node

{

    int fun;

    int d;

    int k;

}s[];

bool cmp(node a,node b)

{

    return a.k>b.k;

}

int main()

{

    int n;RI(n);

    rep(i,,n)

    RI(s[i].fun);

    rep(i,,n)

    RI(s[i].d);

    long maxx=;

    int flag=-;

    rep(i,,n)

    {

        rep(j,,n)

         s[j].k=s[j].fun-s[j].d*(i-);

        sort(s+,s++n,cmp);

        long sum=;

        rep(k,,i)

        sum+=s[k].k;

        if(sum>=maxx)

            maxx=sum;flag=i;

    }

    cout<<maxx<<endl<<flag;

    return ;

}

巴特西

【noip模拟赛4】汽艇模拟

最新文章

热门文章

巴特西

【noip模拟赛4】汽艇 模拟

最新文章

热门文章

【noip模拟赛4】汽艇模拟