[已解决]暴力枚举

Mike_python小

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

1. 有 N（1≤N≤105）头奶牛可能会入学。每头奶牛最多愿意支付 ci 的学费（1≤ci≤10^6）。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量，以及此时应当收取多少学费。
   
2. 
   
3. 输入格式（从终端 / 标准输入读入）：
   
4. 输入的第一行包含 N。第二行包含 N 个整数 c1,c2,…,cN，其中 ci 是奶牛 i 愿意支付的最高学费金额。
   
5. 输出格式（输出至终端 / 标准输出）：
   
6. 输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解，输出收取学费最小的解。
   
7. 注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 "long"，C/C++ 中的 "long long"）。
   
8. 
   
9. 输入样例：
   
10. 4
    
11. 1 6 4 6
    
12. 输出样例：
    
13. 12 4
    
14. 如果 Farmer John 收费 4，那么 3 头奶牛将会入学，从而使他赚取 3÷4=12 的金额。

复制代码

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2022-12-18 10:14:33

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n;
   
5. long long c[100001], res = 0, resc = 1ll << 60, rest = 0;
   
6. 
   
7. int main() {
   
8.         scanf("%d", &n);
   
9.         for (int i = 1; i <= n; ++i) {
   
10.                 scanf("%d", &c[i]);
    
11.         }
    
12.         sort(c + 1, c + n + 1); //属于algorithm
    
13.         for (int i = 1; i <= n; ++i) {
    
14.                 if (c[i] * (n - i + 1) > res) {
    
15.                         res = c[i] * (n - i + 1);
    
16.                 }
    
17.         }
    
18.         for (int i = 1; i <= n; ++i) {
    
19.                 if (res == c[i] * (n - i + 1)) {
    
20.                         resc = min(resc, c[i]); //属于algorithm
    
21.                 }
    
22.         }
    
23.         printf("%lld %lld", res, resc);
    
24.        
    
25. }

复制代码

跳转到最佳答案楼层

zhangjinxuan

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n;
   
5. long long c[100001], res = 0, resc = 1ll << 60, rest = 0;
   
6. 
   
7. int main() {
   
8.         scanf("%d", &n);
   
9.         for (int i = 1; i <= n; ++i) {
   
10.                 scanf("%d", &c[i]);
    
11.         }
    
12.         sort(c + 1, c + n + 1); //属于algorithm
    
13.         for (int i = 1; i <= n; ++i) {
    
14.                 if (c[i] * (n - i + 1) > res) {
    
15.                         res = c[i] * (n - i + 1);
    
16.                 }
    
17.         }
    
18.         for (int i = 1; i <= n; ++i) {
    
19.                 if (res == c[i] * (n - i + 1)) {
    
20.                         resc = min(resc, c[i]); //属于algorithm
    
21.                 }
    
22.         }
    
23.         printf("%lld %lld", res, resc);
    
24.        
    
25. }

复制代码

Mike_python小

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int n;
   
6. long long c[10001];
   
7. long long xue_fei=0;
   
8. long long shou_fei=0;
   
9. long long a=0, temp=0, jishu=0;
   
10. 
    
11. int panduan() {
    
12.     for(int i=0;i<n;i++) {
    
13.         a=0;
    
14.         temp=0;
    
15.         for(int j=0;j<n;j++) {
    
16.             if(c[j]>=c[i]) {
    
17.                 a+=c[i];
    
18.                 temp++;
    
19.             }
    
20.         }
    
21.         if (a>xue_fei) {
    
22.             xue_fei=a;
    
23.             shou_fei=c[i];
    
24.             jishu=temp;
    
25. 
    
26.         }
    
27.         else if(a==xue_fei) {
    
28.             if(temp>=jishu) {
    
29.                 xue_fei=a;
    
30.                 shou_fei=c[i];
    
31.                 jishu=temp;
    
32. //                cout << "i:" << i << ",a:" << a << ",temp:" << temp << endl;
    
33. 
    
34.             }
    
35.         }
    
36. 
    
37. 
    
38.     }
    
39.     cout << xue_fei << " " << shou_fei;
    
40. }
    
41. 
    
42. int main() {
    
43.      cin >> n;
    
44.      for (int i=0;i<n;i++) {
    
45.          cin >> c[i];
    
46.      }
    
47.     panduan();
    
48. 
    
49. }

复制代码

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

tommyyu

1. #include <stdio.h>
   
2. #define MAXN 110
   
3. #define ll long long
   
4. 
   
5. int cows[MAXN];
   
6. int main()
   
7. {
   
8.         int n; scanf("%d", &n);
   
9.         for(int i=0; i<n; ++i) {
   
10.                 int temp; scanf("%d", &temp);
    
11.                 cows[temp]++;
    
12.         }
    
13.        
    
14.         ll max_ = -1;
    
15.         int lower = 0;
    
16.         int max_money;
    
17.         for(int i=0; i<MAXN; ++i) {
    
18.                 if(!cows[i]) continue;
    
19.                 if(!(n-lower)) break;
    
20.                 ll t = ((ll) (n-lower) * i);
    
21.                 if(t > max_){
    
22.                         max_ = t;
    
23.                         max_money = i;
    
24.                 }
    
25.                 lower += cows[i];
    
26.         }
    
27.         printf("%d %d", max_, max_money);
    
28.         return 0;
    
29. }

复制代码

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 没有额外限制。

这个呢

1. #include <stdio.h>
   
2. #define MAXN 10010
   
3. #define ll long long
   
4. 
   
5. int cows[MAXN];
   
6. int main()
   
7. {
   
8.         ll n; scanf("%lld", &n);
   
9.         for(int i=0; i<n; ++i) {
   
10.                 ll temp; scanf("%lld", &temp);
    
11.                 cows[temp]++;
    
12.         }
    
13.        
    
14.         ll max_ = -1;
    
15.         ll lower = 0;
    
16.         ll max_money;
    
17.         for(ll i=0; i<MAXN; ++i) {
    
18.                 if(!cows[i]) continue;
    
19.                 if(!(n-lower)) break;
    
20.                 ll t = ((ll) (n-lower) * i);
    
21.                 if(t > max_){
    
22.                         max_ = t;
    
23.                         max_money = i;
    
24.                 }
    
25.                 lower += cows[i];
    
26.         }
    
27.         printf("%lld %lld", max_, max_money);
    
28.         return 0;
    
29. }

复制代码

Mike_python小

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

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

tommyyu

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

这个呢

1. #include <stdio.h>
   
2. #define MAXN 10010
   
3. #define ll long long
   
4. 
   
5. ll cows[MAXN];
   
6. int main()
   
7. {
   
8.         ll n; scanf("%lld", &n);
   
9.         for(int i=0; i<n; ++i) {
   
10.                 ll temp; scanf("%lld", &temp);
    
11.                 cows[temp]++;
    
12.         }
    
13.        
    
14.         ll max_ = -1;
    
15.         ll lower = 0;
    
16.         ll max_money;
    
17.         for(ll i=0; i<MAXN; ++i) {
    
18.                 if(!cows[i]) continue;
    
19.                 if(!(n-lower)) break;
    
20.                 ll t = ((ll) (n-lower) * i);
    
21.                 if(t > max_){
    
22.                         max_ = t;
    
23.                         max_money = i;
    
24.                 }
    
25.                 lower += cows[i];
    
26.         }
    
27.         printf("%lld %lld", max_, max_money);
    
28.         return 0;
    
29. }

复制代码

Mike_python小

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

和上一次一样

tommyyu

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

那这个呢

1. #include <stdio.h>
   
2. #define MAXN 100010
   
3. #define ll long long
   
4. 
   
5. ll cows[MAXN];
   
6. int main()
   
7. {
   
8.         ll n; scanf("%lld", &n);
   
9.         for(int i=0; i<n; ++i) {
   
10.                 ll temp; scanf("%lld", &temp);
    
11.                 cows[temp]++;
    
12.         }
    
13.        
    
14.         ll max_ = -1;
    
15.         ll lower = 0;
    
16.         ll max_money;
    
17.         for(ll i=0; i<MAXN; ++i) {
    
18.                 if(!cows[i]) continue;
    
19.                 if(!(n-lower)) break;
    
20.                 ll t = ((ll) (n-lower) * i);
    
21.                 if(t > max_){
    
22.                         max_ = t;
    
23.                         max_money = i;
    
24.                 }
    
25.                 lower += cows[i];
    
26.         }
    
27.         printf("%lld %lld", max_, max_money);
    
28.         return 0;
    
29. }

复制代码

Mike_python小

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

还是一样的结果

jhq999

1. 
   
2. int cmp(void* a,void *b)
   
3. {
   
4.     return *(int*)b-*(int*)a;
   
5. }
   
6. int main()
   
7. {
   
8.     int N,max,i;
   
9.     scanf("%d",&N);
   
10.     int ci[N];
    
11.     for(int i=0;i<N;i+=1)scanf("%d",&ci[i]);
    
12.     qsort(ci,N,sizeof(int),cmp);
    
13.     for(i=0,max=ci[0];i<N&&max<=(i+1)*ci[i];i+=1)
    
14.     {
    
15.         if(max<(i+1)*ci[i])max=(i+1)*ci[i];
    
16.         printf("%d ",ci[i]);
    
17.     }
    
18.     printf("\n%d %d",i*ci[i-1],ci[i-1]);
    
19.     return 0;
    
20. }

复制代码

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

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

复制代码

报错

jhq999

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

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int n;
   
6. long long c[1000001];
   
7. long long xue_fei=0;
   
8. long long shou_fei=0;
   
9. long long a=0, temp=0, jishu=0;
   
10. 
    
11. int panduan()
    
12. {
    
13.     temp=a*c[a];
    
14.     int i;
    
15.     for(i=a,a=c[a]; i>0; i-=1,a+=c[i])
    
16.     {
    
17.         if(c[i])
    
18.         {
    
19. 
    
20.             if(temp>a*i)break;
    
21.             xue_fei=i;
    
22.         }
    
23. 
    
24.     }
    
25.     printf("%lld %lld",temp,xue_fei);
    
26. }
    
27. 
    
28. int main()
    
29. {
    
30.     cin >> n;
    
31.     for (int i=0; i<n; i++)
    
32.     {
    
33.         cin >> temp;
    
34.         if(temp>a)a=temp;
    
35.         c[temp]+=1;
    
36.     }
    
37.     panduan();
    
38. 
    
39. }

复制代码

Mike_python小

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

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

jhq999

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

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. int cmp(const void* a,const void *b)
   
5. {
   
6.     return *(int*)b-*(int*)a;
   
7. }
   
8. int main()
   
9. {
   
10.     int N,max,i;
    
11.     scanf("%d",&N);
    
12.     int ci[N];
    
13.     for(int i=0;i<N;i+=1)scanf("%d",&ci[i]);
    
14.     qsort(&ci,N,sizeof(int),cmp);
    
15.     for(i=0,max=ci[0];i<N&&max<=(i+1)*ci[i];i+=1)
    
16.     {
    
17.         if(max<(i+1)*ci[i])max=(i+1)*ci[i];
    
18.         printf("%d ",ci[i]);
    
19.     }
    
20.     printf("\n%d %d",i*ci[i-1],ci[i-1]);
    
21.     return 0;
    
22. }
    

复制代码

Mike_python小

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

az我要用C++解

jhq999

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

等一会，转移一下

1. #include <iostream>
   
2. using namespace std;
   
3. int ci[106];
   
4. int cmp(const void* a,const void *b)
   
5. {
   
6.     return *(int*)b-*(int*)a;
   
7. }
   
8. int main()
   
9. {
   
10.     int N,max,i;
    
11.     cin>>N;
    
12.     for(i=0;i<N;i+=1)cin>>ci[i];
    
13.     qsort(&ci,N,sizeof(int),cmp);
    
14.     for(i=0,max=ci[0];i<N&&max<=(i+1)*ci[i];i+=1)
    
15.     {
    
16.         if(max<(i+1)*ci[i])max=(i+1)*ci[i];
    
17.     }
    
18.     cout<<i*ci[i-1]<<" "<<ci[i-1]<<endl;
    
19.     return 0;
    
20. }
    

复制代码