暴力枚举
本帖最后由 Mike_python小 于 2022-12-18 11:02 编辑昨天参加了一个竞赛，有一道题永枚举的办法没得到全部分，求助一下不用枚举的做法
有 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 的金额。
打了14个点的蒟蒻申请出战{:10_282:}
#include <bits/stdc++.h>
using namespace std;
int n;
long long c, res = 0, resc = 1ll << 60, rest = 0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &c);
}
sort(c + 1, c + n + 1); //属于algorithm
for (int i = 1; i <= n; ++i) {
if (c * (n - i + 1) > res) {
res = c * (n - i + 1);
}
}
for (int i = 1; i <= n; ++i) {
if (res == c * (n - i + 1)) {
resc = min(resc, c); //属于algorithm
}
}
printf("%lld %lld", res, resc);
} #include <iostream>
using namespace std;
int n;
long long c;
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>=c) {
a+=c;
temp++;
}
}
if (a>xue_fei) {
xue_fei=a;
shou_fei=c;
jishu=temp;
}
else if(a==xue_fei) {
if(temp>=jishu) {
xue_fei=a;
shou_fei=c;
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;
}
panduan();
}
这是我的狗屎代码，他错误了几个，超出运行内存或时间了几个 #include <stdio.h>
#define MAXN 110
#define ll long long
int cows;
int main()
{
int n; scanf("%d", &n);
for(int i=0; i<n; ++i) {
int temp; scanf("%d", &temp);
cows++;
}
ll max_ = -1;
int lower = 0;
int max_money;
for(int i=0; i<MAXN; ++i) {
if(!cows) continue;
if(!(n-lower)) break;
ll t = ((ll) (n-lower) * i);
if(t > max_){
max_ = t;
max_money = i;
}
lower += cows;
}
printf("%d %d", max_, max_money);
return 0;
} tommyyu 发表于 2022-12-18 10:55
测试点1是正确的（输入样例：
4
1 6 4 6
输出样例：
12 4）
之后的2-4是错误的，5-12是超出运行时错误或内存限制 tommyyu 发表于 2022-12-18 10:55
测试点 2-4 满足 ci≤1,000。
测试点 5-8 满足 N≤5,000。
测试点 9-12 没有额外限制。 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;
int main()
{
ll n; scanf("%lld", &n);
for(int i=0; i<n; ++i) {
ll temp; scanf("%lld", &temp);
cows++;
}
ll max_ = -1;
ll lower = 0;
ll max_money;
for(ll i=0; i<MAXN; ++i) {
if(!cows) continue;
if(!(n-lower)) break;
ll t = ((ll) (n-lower) * i);
if(t > max_){
max_ = t;
max_money = i;
}
lower += cows;
}
printf("%lld %lld", max_, max_money);
return 0;
} tommyyu 发表于 2022-12-18 11:03
这个呢
情况好一点，1-4的数据正确，5-12的数据超出运行时错误或内存限制（并非时间限制) Mike_python小 发表于 2022-12-18 11:05
情况好一点，1-4的数据正确，5-12的数据超出运行时错误或内存限制（并非时间限制)
{:10_282:}这个呢#include <stdio.h>
#define MAXN 10010
#define ll long long
ll cows;
int main()
{
ll n; scanf("%lld", &n);
for(int i=0; i<n; ++i) {
ll temp; scanf("%lld", &temp);
cows++;
}
ll max_ = -1;
ll lower = 0;
ll max_money;
for(ll i=0; i<MAXN; ++i) {
if(!cows) continue;
if(!(n-lower)) break;
ll t = ((ll) (n-lower) * i);
if(t > max_){
max_ = t;
max_money = i;
}
lower += cows;
}
printf("%lld %lld", max_, max_money);
return 0;
} tommyyu 发表于 2022-12-18 11:08
这个呢
和上一次一样{:10_250:} Mike_python小 发表于 2022-12-18 11:10
和上一次一样
{:10_282:}那这个呢#include <stdio.h>
#define MAXN 100010
#define ll long long
ll cows;
int main()
{
ll n; scanf("%lld", &n);
for(int i=0; i<n; ++i) {
ll temp; scanf("%lld", &temp);
cows++;
}
ll max_ = -1;
ll lower = 0;
ll max_money;
for(ll i=0; i<MAXN; ++i) {
if(!cows) continue;
if(!(n-lower)) break;
ll t = ((ll) (n-lower) * i);
if(t > max_){
max_ = t;
max_money = i;
}
lower += cows;
}
printf("%lld %lld", max_, max_money);
return 0;
} tommyyu 发表于 2022-12-18 11:20
那这个呢
还是一样的结果{:10_250:}
int cmp(void* a,void *b)
{
return *(int*)b-*(int*)a;
}
int main()
{
int N,max,i;
scanf("%d",&N);
int ci;
for(int i=0;i<N;i+=1)scanf("%d",&ci);
qsort(ci,N,sizeof(int),cmp);
for(i=0,max=ci;i<N&&max<=(i+1)*ci;i+=1)
{
if(max<(i+1)*ci)max=(i+1)*ci;
printf("%d ",ci);
}
printf("\n%d %d",i*ci,ci);
return 0;
} jhq999 发表于 2022-12-18 11:27
我是小白，请问qsort用什么头文件？我用#include <stdlib.h>他显示No matching function for call to 'qsort' 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);
~~~~~^~~~~~~~~~~~~
报错 Mike_python小 发表于 2022-12-18 11:36
报错
#include <iostream>
using namespace std;
int n;
long long c;
long long xue_fei=0;
long long shou_fei=0;
long long a=0, temp=0, jishu=0;
int panduan()
{
temp=a*c;
int i;
for(i=a,a=c; i>0; i-=1,a+=c)
{
if(c)
{
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+=1;
}
panduan();
} jhq999 发表于 2022-12-18 11:58
只有测试点1是正确的，其余是错误的 本帖最后由 jhq999 于 2022-12-18 12:30 编辑
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;
for(int i=0;i<N;i+=1)scanf("%d",&ci);
qsort(&ci,N,sizeof(int),cmp);
for(i=0,max=ci;i<N&&max<=(i+1)*ci;i+=1)
{
if(max<(i+1)*ci)max=(i+1)*ci;
printf("%d ",ci);
}
printf("\n%d %d",i*ci,ci);
return 0;
}
jhq999 发表于 2022-12-18 12:25
az我要用C++解 本帖最后由 jhq999 于 2022-12-18 12:43 编辑
Mike_python小 发表于 2022-12-18 12:31
az我要用C++解
等一会，转移一下
#include <iostream>
using namespace std;
int ci;
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;
qsort(&ci,N,sizeof(int),cmp);
for(i=0,max=ci;i<N&&max<=(i+1)*ci;i+=1)
{
if(max<(i+1)*ci)max=(i+1)*ci;
}
cout<<i*ci<<" "<<ci<<endl;
return 0;
}
页:
[1]
2