https://www.acwing.com/problem/content/5367/
题目如果只需要输出最大值，我都没有问题。每次需要输出方案的时候,我似乎都需要先统计最大值，再重新扫描一遍找所有能够取得最大值的方案，然后在这些方案中找到最大值。最好的做法应该是在找最大值的过程中就维护题目要求方案的排序关键字，有时候这个关键字不是我们枚举顺序能决定的，我们就需要单独处理。
// Problem: 奶牛报数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5367/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n+1;i<=2*n;i++)a[i]=a[i-n];
int l,r;cin>>l>>r;
//int len=r-1-l+1;
//枚举哪个位置牛报1号
for(int i=1;i<=2*n;i++)a[i]+=a[i-1];
//for(int i=1;i<=2*n;i++)cerr<<a[i]<<" ";
//cerr<<endl;
int mx=0,pos=1;
for(int i=1;i<=n;i++){
int tmp=a[i+r-1-1]-a[i+l-2];
//cerr<<mx<<endl;
if(mx<tmp){
mx=tmp;
pos=i;
}
}
int ans=mx;
int res=1e9;
//vector<int>v;
for(int i=1;i<=n;i++){
int tmp=a[i+r-1-1]-a[i+l-2];
if(tmp==mx)res=min(res,n+2-i);
}
if(res>n)res-=n;
cout<<res<<endl;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
t=1;
while (t--) {
solve();
}
return 0;
}
上面是实现比较繁琐的代码。
下面给出 边求最大值 边维护题目要求关键字 的方案 的代码
// Problem: 奶牛报数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5367/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int get(int pos){
int res=n+2-pos;
if(res>n)res-=n;
return res;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n+1;i<=2*n;i++)a[i]=a[i-n];
int l,r;cin>>l>>r;
//int len=r-1-l+1;
//枚举哪个位置牛报1号
for(int i=1;i<=2*n;i++)a[i]+=a[i-1];
//for(int i=1;i<=2*n;i++)cerr<<a[i]<<" ";
//cerr<<endl;
int mx=-1,pos=1e9;
for(int i=1;i<=n;i++){
int tmp=a[i+r-1-1]-a[i+l-2];
//cerr<<mx<<endl;
if(mx<tmp||(mx==tmp&&get(i)<get(pos))){
mx=tmp;
pos=i;
}
}
// int ans=mx;
// int res=1e9;
//vector<int>v;
// for(int i=1;i<=n;i++){
// int tmp=a[i+r-1-1]-a[i+l-2];
// if(tmp==mx)res=min(res,n+2-i);
// }
// if(res>n)res-=n;
cout<<get(pos)<<endl;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
t=1;
while (t--) {
solve();
}
return 0;
}
这道题目维护的get（i），也就是所有方案中get（i）的最小值，所以在比较最大值相等的过程中只需要在比较一下get（i）。
那我们为什么不直接从小到大枚举这个关键字呢，虽然只需要找到一个反函数映射回去，但是正着枚举思路实现思路更自然清晰。