题目链接：点击打开链接
题目大意：题目有点拗口，多读几遍那核心语句，注意是当中的“超过”一词，不能加等号。
解题思路：AC1：差分后缀和 + 二分比较； AC2：普通模拟（如果数据再大点可能会TLE）。
AC1 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1e5+10; unordered_map<int,int> ump; int a[maxn], w[maxn]; int main() { int n,b,l=0; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&b); if(ump[b]==0) a[++l]=b; ump[b]++; } sort(a+1,a+l+1); w[l]=ump[a[l]]; for(int i=l-1;i>0;i--) w[i]=ump[a[i]]+w[i+1]; w[0]=2*w[1]; int p=l-1, rs=-1, d; while(p>=0) { d=w[p]-ump[a[p]]; if(d>=a[p]) { rs=a[p]; int l=a[p]+1, r=a[p+1]-1, m; while(l<=r) { m=l+((r-l)>>1); if(d>=m) rs=m, l=m+1; else r=m-1; } break; } else p--; } printf("%d\n",rs); return 0; }
AC2 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; int main() { int n; scanf("%d",&n); int a[n+5]; for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1,greater<int>()); int ans=0, p=1; while(ans<=n && a[p]>p) ans++, p++; // ans 表示满足的最多天数，p 表示英里数（超过） printf("%d\n",ans); return 0; }
