[已解决]暴力枚举

Mike_python小

昨天参加了一个竞赛，有一道题永枚举的办法没得到全部分，求助一下不用枚举的做法

有 N（1≤N≤105）头奶牛可能会入学。每头奶牛最多愿意支付 ci 的学费（1≤ci≤10^6）。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量，以及此时应当收取多少学费。

输入格式（从终端 / 标准输入读入）：
输入的第一行包含 N。第二行包含 N 个整数 c1,c2,…,cN，其中 ci 是奶牛 i 愿意支付的最高学费金额。
输出格式（输出至终端 / 标准输出）：
输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解，输出收取学费最小的解。
注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 "long"，C/C++ 中的 "long long"）。

输入样例：
4
1 6 4 6
输出样例：
12 4
如果 Farmer John 收费 4，那么 3 头奶牛将会入学，从而使他赚取 3÷4=12 的金额。

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2022-12-18 10:14:33

打了14个点的蒟蒻申请出战

#include <bits/stdc++.h>
using namespace std;

int n;
long long c[100001], res = 0, resc = 1ll << 60, rest = 0;

int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
                scanf("%d", &c[i]);
        }
        sort(c + 1, c + n + 1); //属于algorithm
        for (int i = 1; i <= n; ++i) {
                if (c[i] * (n - i + 1) > res) {
                        res = c[i] * (n - i + 1);
                }
        }
        for (int i = 1; i <= n; ++i) {
                if (res == c[i] * (n - i + 1)) {
                        resc = min(resc, c[i]); //属于algorithm
                }
        }
        printf("%lld %lld", res, resc);
        
}

跳转到最佳答案楼层

zhangjinxuan

打了14个点的蒟蒻申请出战

#include <bits/stdc++.h>
using namespace std;

int n;
long long c[100001], res = 0, resc = 1ll << 60, rest = 0;

int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
                scanf("%d", &c[i]);
        }
        sort(c + 1, c + n + 1); //属于algorithm
        for (int i = 1; i <= n; ++i) {
                if (c[i] * (n - i + 1) > res) {
                        res = c[i] * (n - i + 1);
                }
        }
        for (int i = 1; i <= n; ++i) {
                if (res == c[i] * (n - i + 1)) {
                        resc = min(resc, c[i]); //属于algorithm
                }
        }
        printf("%lld %lld", res, resc);
        
}

Mike_python小

#include <iostream>

using namespace std;

int n;
long long c[10001];
long long xue_fei=0;
long long shou_fei=0;
long long a=0, temp=0, jishu=0;

int panduan() {
    for(int i=0;i<n;i++) {
        a=0;
        temp=0;
        for(int j=0;j<n;j++) {
            if(c[j]>=c[i]) {
                a+=c[i];
                temp++;
            }
        }
        if (a>xue_fei) {
            xue_fei=a;
            shou_fei=c[i];
            jishu=temp;

        }
        else if(a==xue_fei) {
            if(temp>=jishu) {
                xue_fei=a;
                shou_fei=c[i];
                jishu=temp;
//                cout << "i:" << i << ",a:" << a << ",temp:" << temp << endl;

            }
        }


    }
    cout << xue_fei << " " << shou_fei;
}

int main() {
     cin >> n;
     for (int i=0;i<n;i++) {
         cin >> c[i];
     }
    panduan();

}

这是我的狗屎代码，他错误了几个，超出运行内存或时间了几个

tommyyu

#include <stdio.h>
#define MAXN 110
#define ll long long

int cows[MAXN];
int main()
{
        int n; scanf("%d", &n);
        for(int i=0; i<n; ++i) {
                int temp; scanf("%d", &temp);
                cows[temp]++;
        }
        
        ll max_ = -1;
        int lower = 0;
        int max_money;
        for(int i=0; i<MAXN; ++i) {
                if(!cows[i]) continue;
                if(!(n-lower)) break;
                ll t = ((ll) (n-lower) * i);
                if(t > max_){
                        max_ = t;
                        max_money = i;
                }
                lower += cows[i];
        }
        printf("%d %d", max_, max_money);
        return 0;
}

Mike_python小

tommyyu 发表于 2022-12-18 10:55

测试点1是正确的（输入样例：
4
1 6 4 6
输出样例：
12 4）

之后的2-4是错误的，5-12是超出运行时错误或内存限制

Mike_python小

tommyyu 发表于 2022-12-18 10:55

测试点 2-4 满足 ci≤1,000。
测试点 5-8 满足 N≤5,000。
测试点 9-12 没有额外限制。

tommyyu

Mike_python小 发表于 2022-12-18 11:00
测试点 2-4 满足 ci≤1,000。
测试点 5-8 满足 N≤5,000。
测试点 9-12 没有额外限制。

这个呢

#include <stdio.h>
#define MAXN 10010
#define ll long long

int cows[MAXN];
int main()
{
        ll n; scanf("%lld", &n);
        for(int i=0; i<n; ++i) {
                ll temp; scanf("%lld", &temp);
                cows[temp]++;
        }
        
        ll max_ = -1;
        ll lower = 0;
        ll max_money;
        for(ll i=0; i<MAXN; ++i) {
                if(!cows[i]) continue;
                if(!(n-lower)) break;
                ll t = ((ll) (n-lower) * i);
                if(t > max_){
                        max_ = t;
                        max_money = i;
                }
                lower += cows[i];
        }
        printf("%lld %lld", max_, max_money);
        return 0;
}

Mike_python小

tommyyu 发表于 2022-12-18 11:03
这个呢

情况好一点，1-4的数据正确，5-12的数据超出运行时错误或内存限制（并非时间限制)

tommyyu

Mike_python小 发表于 2022-12-18 11:05
情况好一点，1-4的数据正确，5-12的数据超出运行时错误或内存限制（并非时间限制)

这个呢

#include <stdio.h>
#define MAXN 10010
#define ll long long

ll cows[MAXN];
int main()
{
        ll n; scanf("%lld", &n);
        for(int i=0; i<n; ++i) {
                ll temp; scanf("%lld", &temp);
                cows[temp]++;
        }
        
        ll max_ = -1;
        ll lower = 0;
        ll max_money;
        for(ll i=0; i<MAXN; ++i) {
                if(!cows[i]) continue;
                if(!(n-lower)) break;
                ll t = ((ll) (n-lower) * i);
                if(t > max_){
                        max_ = t;
                        max_money = i;
                }
                lower += cows[i];
        }
        printf("%lld %lld", max_, max_money);
        return 0;
}

Mike_python小

tommyyu 发表于 2022-12-18 11:08
这个呢

和上一次一样

tommyyu

Mike_python小 发表于 2022-12-18 11:10
和上一次一样

那这个呢

#include <stdio.h>
#define MAXN 100010
#define ll long long

ll cows[MAXN];
int main()
{
        ll n; scanf("%lld", &n);
        for(int i=0; i<n; ++i) {
                ll temp; scanf("%lld", &temp);
                cows[temp]++;
        }
        
        ll max_ = -1;
        ll lower = 0;
        ll max_money;
        for(ll i=0; i<MAXN; ++i) {
                if(!cows[i]) continue;
                if(!(n-lower)) break;
                ll t = ((ll) (n-lower) * i);
                if(t > max_){
                        max_ = t;
                        max_money = i;
                }
                lower += cows[i];
        }
        printf("%lld %lld", max_, max_money);
        return 0;
}

Mike_python小

tommyyu 发表于 2022-12-18 11:20
那这个呢

还是一样的结果

jhq999

int cmp(void* a,void *b)
{
    return *(int*)b-*(int*)a;
}
int main()
{
    int N,max,i;
    scanf("%d",&N);
    int ci[N];
    for(int i=0;i<N;i+=1)scanf("%d",&ci[i]);
    qsort(ci,N,sizeof(int),cmp);
    for(i=0,max=ci[0];i<N&&max<=(i+1)*ci[i];i+=1)
    {
        if(max<(i+1)*ci[i])max=(i+1)*ci[i];
        printf("%d ",ci[i]);
    }
    printf("\n%d %d",i*ci[i-1],ci[i-1]);
    return 0;
}

Mike_python小

jhq999 发表于 2022-12-18 11:27

我是小白，请问qsort用什么头文件？我用#include <stdlib.h>他显示No matching function for call to 'qsort'

Mike_python小

jhq999 发表于 2022-12-18 11:27

main.cpp: In function ‘int main()’:
main.cpp:18:31: error: invalid conversion from ‘int (*)(void*, void*)’ to ‘__compar_fn_t {aka int (*)(const void*, const void*)}’ [-fpermissive]
     qsort(ci,N,sizeof(int),cmp);
                               ^
In file included from /usr/include/c++/7/cstdlib:75:0,
                 from /usr/include/c++/7/ext/string_conversions.h:41,
                 from /usr/include/c++/7/bits/basic_string.h:6361,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from main.cpp:1:
/usr/include/stdlib.h:827:13: note:   initializing argument 4 of ‘void qsort(void*, size_t, size_t, __compar_fn_t)’
 extern void qsort (void *__base, size_t __nmemb, size_t __size,
             ^~~~~
main.cpp:15:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
main.cpp:17:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<N;i+=1)scanf("%d",&ci[i]);
                          ~~~~~^~~~~~~~~~~~~

报错

jhq999

Mike_python小 发表于 2022-12-18 11:36
报错

#include <iostream>

using namespace std;

int n;
long long c[1000001];
long long xue_fei=0;
long long shou_fei=0;
long long a=0, temp=0, jishu=0;

int panduan()
{
    temp=a*c[a];
    int i;
    for(i=a,a=c[a]; i>0; i-=1,a+=c[i])
    {
        if(c[i])
        {

            if(temp>a*i)break;
            xue_fei=i;
        }

    }
    printf("%lld %lld",temp,xue_fei);
}

int main()
{
    cin >> n;
    for (int i=0; i<n; i++)
    {
        cin >> temp;
        if(temp>a)a=temp;
        c[temp]+=1;
    }
    panduan();

}

Mike_python小

jhq999 发表于 2022-12-18 11:58

只有测试点1是正确的，其余是错误的

jhq999

Mike_python小 发表于 2022-12-18 11:36
报错

#include<stdio.h>
#include<stdlib.h>

int cmp(const void* a,const void *b)
{
    return *(int*)b-*(int*)a;
}
int main()
{
    int N,max,i;
    scanf("%d",&N);
    int ci[N];
    for(int i=0;i<N;i+=1)scanf("%d",&ci[i]);
    qsort(&ci,N,sizeof(int),cmp);
    for(i=0,max=ci[0];i<N&&max<=(i+1)*ci[i];i+=1)
    {
        if(max<(i+1)*ci[i])max=(i+1)*ci[i];
        printf("%d ",ci[i]);
    }
    printf("\n%d %d",i*ci[i-1],ci[i-1]);
    return 0;
}

Mike_python小

jhq999 发表于 2022-12-18 12:25

az我要用C++解

jhq999

Mike_python小 发表于 2022-12-18 12:31
az我要用C++解

等一会，转移一下

#include <iostream>
using namespace std;
int ci[106];
int cmp(const void* a,const void *b)
{
    return *(int*)b-*(int*)a;
}
int main()
{
    int N,max,i;
    cin>>N;
    for(i=0;i<N;i+=1)cin>>ci[i];
    qsort(&ci,N,sizeof(int),cmp);
    for(i=0,max=ci[0];i<N&&max<=(i+1)*ci[i];i+=1)
    {
        if(max<(i+1)*ci[i])max=(i+1)*ci[i];
    }
    cout<<i*ci[i-1]<<" "<<ci[i-1]<<endl;
    return 0;
}