宣传一下春季每日一题题解
老久之前写的题解了,最近发现点赞数突然增加,原来又是每日一题造的孽。
之前写的过于粗糙,现在(2024.3.5)进行略微修改。
先二分,再 sort,随后给每个 ≤h 的数加 1,直到 l==0,再二分一次求 ans。
但是在 USACO 过不了,因为要开 long long……
这里感谢大神们给出的提示,大家一定要注意这些溢出的问题。
另外请注意二分的写法,错误写法容易死循环,具体可以参考这里。
时间复杂度 O(NlogN)。
#include <bits/stdc++.h>
using namespace std;
int n, k, c[100010];
int check(int x) { //求h是否成立
int ans = 0;
for (int i = 1;i <= n; i++) if (c[i] >= x) ans++;
return ans >= x;
}
int main() {
scanf("%d%d", &n, &k);
int l = 100010, r = 0;
for (int i = 1; i <= n; i++) scanf("%d", &c[i]), l = min(l, c[i]), r = max(r, c[i]);
while (l < r) {
int mid = l + r + 1 >> 1;
if (!check(mid)) r = mid - 1;
else l = mid;
}
sort(c + 1, c + 1 + n);
for (int i = n;i > 0; i--) {
if (k == 0) break;
if (c[i] <= l) c[i]++, k--;
}
l = 0, r = 100000;
while (l < r) {
int mid = l + r + 1 >> 1;
if (!check(mid)) r = mid - 1;
else l = mid;
}
printf("%d", l);
return 0;
}
接着是我的第二种解法,就是统计一下每个引用次数的cnt(出现次数),然后就 for循环一遍 0~n。
这里的 for 循环 ans 只是到了 n,是因为:
h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h。
显然 h 一定不会超过总篇数 n。
那这样就可以统计了,代码实现也挺简单。
另外感谢 @JcWing 大佬指出的问题,这里的 map 确实是多余的,可以修改为数组。
这样复杂度还能省掉一个 log,千万不要问我为什么我几年前那么弱智。
但是我懒得写了,大家应该都知道怎么改吧?
时间复杂度 O(N),没错下面是带 log 大常数的做法。
#include <bits/stdc++.h>
using namespace std;
map<int, int> cnt;
int main() {
int n, l; scanf("%d%d", &n, &l);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
cnt[x]++;
}
int ans = 0, x = n;
for (ans = 0; ans < n; ans++) {
x -= cnt[ans];
if (x + min(cnt[ans], l) <= ans) break;
} printf("%d\n", ans);
return 0;
}
#include <bits/stdc++.h> using namespace std; const int N = 100010; int n, m;//n篇论文,最多可以引用m篇论文 int c[N]; bool check(int mid) { int cnt = 0, backup = m; for (int i = 0; i < n; i ++) { if (c[i] >= mid) cnt ++; else if (backup && c[i] + 1 >= mid) cnt ++, backup --; } return cnt >= mid; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); cin >> n >> m; for (int i = 0; i < n; i ++) cin >> c[i]; int l = 0, r = 1e5; while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } cout << l << '\n'; return 0; }
妙啊,直接check答案
为什么不用排序??
统计够不够就可以了,不需要排序
!懂了懂了
cnt是什么
因为相当于做了一次桶排序
记录个数的,够不够mid个
太妙了
bool check(int mid){
int res = 0;
for(int i = 0;i < n;i){
if(a[i] >= mid) res;
else if(m && a[i] + 1 >= mid){
res++;
m–;
}
}
return res >= mid;
}
为什么这里直接用m会有一个测试点过不了
会进行多次check,要保证每次进入check的时候m都是相同的。所以要备份一下
懂了哈哈,谢谢
为什么我感觉有点问题呢,在check的elseif里如果每次需要backup加的是2怎么办呢,比如说 2 4 0 0 是不是每次需要加2,怎么判断啊
题意有限制(她只能引用每篇她的论文至多一次。)
x -= cnt[ans] 之后,x表示:引用量 > ans 的文章的篇数
x + min(cnt[ans], l) 表示:引用量包括ans的或是加上L个引用之后引用量> ans的文章的篇数
记录一下每个数出现的次数然后前缀和就行了,别的不需要;
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; typedef long long ll; typedef pair<int,int> PII; int n,m;int a[N],id,maxn; int main() { ios::sync_with_stdio(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>id,a[id]++,maxn=max(maxn,id); for(int i=1;i<=maxn+5;i++) { a[i]+=a[i-1]; int sum=0; sum+=n-a[i-1]; //cout<<sum<<' '; if(i>=2) sum+=min(m,a[i-1]-a[i-2]); else sum+=min(m,a[i-1]); if(sum<i) { cout<<i-1;return 0; } } return 0; }
虽然但是,大佬能讲解一下吗,orz
第二种做法不用开 map 吧,数据范围说了输入的每个数 ≤105 ,开个数组应该就够了。这样时间复杂度还能省一个 log
我的ac代码也很玄学
#include<iostream> #include<algorithm> #include<string.h> using namespace std; #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl typedef pair<int,int> pii; typedef long long ll; const double eps=1e-8; const int INF=0x3f3f3f3f; const int N=100005; int c[N]; int jishu[N]; int s[N]; int l; int n; int main() { scanf("%d%d",&n,&l); for(int i=1;i<=n;i++) { scanf("%d",&c[i]); jishu[c[i]]++; } for(int i=100000;i>=0;i--) { s[i]=s[i+1]+jishu[i]; } int res=-1; for(int i=100000;i>=0;i--) { if(s[i+1]<=i+1) res=max(res,s[i+1]+max(min(min((i+1)-s[i+1],l),jishu[i]),0)); } printf("%d\n",res); }
浅显的写了一下自己的理解:
https://www.acwing.com/solution/content/238301/
比y总讲的好理解
#include[HTML_REMOVED]
using namespace std;
const int N=1e5+10;
int n,m;//
int a[N];
bool check(int mid){
int ans=0;
for(int i=1;i<=mid;i){
if(a[i]>=mid)continue;
else if(a[i]+1>=mid){
ans;
}
}
if(ans>m)return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1,greater[HTML_REMOVED]());
int l=0,r=n;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}
大佬可以帮我看看码
强
妙啊,O(n)的做法
#pragma GCC optimize(3) #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; int tr[N],p[N]; int n,k; int maxv; int lowbit(int x) { return x&-x; } void add(int x,int a) { for(int i=x;i<=N;i=i+lowbit(i)) tr[i]+=a; } int sum(int x) { int res=0; for(int i=x;i;i=i-lowbit(i)) res+=tr[i]; return res; } bool check(int x) { int res=0; res=sum(x-1)-sum(x-2); res=min(res,k); if(sum(maxv)-sum(x-1)+res>=x) return true; else return false; } signed main() { ios::sync_with_stdio(false); cin>>n>>k; for(int i=0;i<n;i++) { cin>>p[i]; p[i]=p[i]+1; maxv=max(p[i],maxv); add(p[i],1); } sort(p,p+n); int l=1,r=n+1; while(l<r) { int mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } cout<<l-1; return 0; }这样写有啥问题 过了一半11/19样例
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
想问一下大佬这一步if (x + min(cnt[ans], l) <= ans) break;的小于等于是怎么想的啊
为啥不能是单纯一个小于
我也不懂
刚学完二分。二分不应该是在数组里通过判断找特定的元素吗,边界 l和r 分别为数组的左右两边。为什么这里的二分l和r是数组元素的最大值最小值?
我有一个疑问,就是如果N个值都是同一个值得,y总讲的那两个判断条件怎么理解呢?
牛牛牛
滴滴,我发现在第二次二分时其左端点l初值要设为0,不然的话过不了呢
oo,Thanks,谢谢大佬的提醒
orz
map是O(logn)的,unordered_mapO(1)你怎么不用,比map快多了
oo谢谢!
太太太太强了,大佬。
偶遇大佬
???大佬大佬