A：显然从大到小排序后贪心放在第一个能放的位置即可。并查集维护。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 300010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,a[N],b[N],id[N],fa[N<<1];
ll ans;
bool cmp(const int&x,const int&y)
{
return a[x]>a[y];
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(),m=read();
for (int i=1;i<=n;i++) id[i]=i,a[i]=read();
sort(id+1,id+n+1,cmp);
for (int i=m+1;i<=m+n+1;i++) fa[i]=i;
for (int i=1;i<=n;i++)
{
b[id[i]]=find(max(m+1,id[i]));
ans+=1ll*a[id[i]]*(b[id[i]]-id[i]);
fa[b[id[i]]]=find(b[id[i]]+1);
}
cout<<ans<<endl;
for (int i=1;i<=n;i++) printf("%d ",b[i]);
return 0;
//NOTICE LONG LONG!!!!!
}
B：对前后缀处理出答案，two pointers即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,k;
ll pre[N],suf[N],cost[N];
bool flag[N];
struct data
{
int t,x,y,c;
bool operator <(const data&a) const
{
return t<a.t;
}
}a[N];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(),m=read(),k=read();
for (int i=1;i<=m;i++)
{
int t=read(),x=read(),y=read(),c=read();
a[i].t=t,a[i].x=x,a[i].y=y,a[i].c=c;
}
sort(a+1,a+m+1);
memset(pre,42,sizeof(pre));int cnt=0;
memset(cost,42,sizeof(cost));
memset(flag,0,sizeof(flag));
for (int i=1;i<=m;i++)
{
pre[i]=pre[i-1];
if (a[i].y==0)
{
if (!flag[a[i].x])
{
cnt++;
cost[a[i].x]=a[i].c;
flag[a[i].x]=1;
if (cnt==n)
{
pre[i]=0;
for (int j=1;j<=n;j++) pre[i]+=cost[j];
}
}
else
if (a[i].c<cost[a[i].x])
{
if (cnt==n) pre[i]-=cost[a[i].x]-a[i].c;
cost[a[i].x]=a[i].c;
}
}
}
memset(suf,42,sizeof(suf));cnt=0;
memset(cost,42,sizeof(cost));
memset(flag,0,sizeof(flag));
for (int i=m;i>=1;i--)
{
suf[i]=suf[i+1];
if (a[i].x==0)
{
if (!flag[a[i].y])
{
cnt++;flag[a[i].y]=1;
cost[a[i].y]=a[i].c;
if (cnt==n)
{
suf[i]=0;
for (int j=1;j<=n;j++) suf[i]+=cost[j];
}
}
else
if (a[i].c<cost[a[i].y])
{
if (cnt==n) suf[i]-=cost[a[i].y]-a[i].c;
cost[a[i].y]=a[i].c;
}
}
}
int x=0;ll ans=pre[0];
for (int i=1;i<=m;i++)
{
while (a[i].t-a[x+1].t>k) x++;
if (x) ans=min(ans,pre[x]+suf[i]);
}
if (ans==pre[0]) cout<<-1;
else cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
C：根据查询矩形边界将平面分成九块，讨论两端点位置即可，主席树支持查询矩形内点的个数。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,q,a[N],root[N],cnt;
struct data{int l,r,x;
}tree[N<<6];
void ins(int &k,int l,int r,int x)
{
tree[++cnt]=tree[k];k=cnt;tree[k].x++;
if (l==r) return;
int mid=l+r>>1;
if (x<=mid) ins(tree[k].l,l,mid,x);
else ins(tree[k].r,mid+1,r,x);
}
int Query(int x,int y,int l,int r,int p,int q)
{
if (!y) return 0;
if (l==p&&r==q) return tree[y].x-tree[x].x;
int mid=l+r>>1;
if (q<=mid) return Query(tree[x].l,tree[y].l,l,mid,p,q);
else if (p>mid) return Query(tree[x].r,tree[y].r,mid+1,r,p,q);
else return Query(tree[x].l,tree[y].l,l,mid,p,mid)+Query(tree[x].r,tree[y].r,mid+1,r,mid+1,q);
}
int query(int l,int r,int x,int y)
{
if (l>r||x>y) return 0;
return Query(root[l-1],root[r],1,n,x,y);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(),q=read();
for (int i=1;i<=n;i++)
{
root[i]=root[i-1];
a[i]=read();
ins(root[i],1,n,a[i]);
}
for (int _=1;_<=q;_++)
{
int l=read(),d=read(),r=read(),u=read();
int x=query(l,r,d,u),f=query(l,r,1,d-1),g=query(l,r,u+1,n);
int v=query(1,l-1,d,n),w=query(1,l-1,1,u);
ll ans=0;
ans+=1ll*f*v;
ans+=1ll*g*w;
ans+=1ll*x*(l-1);
ans+=1ll*(r-l+1)*(r-l)/2;
ans-=1ll*f*(f-1)/2;
ans-=1ll*g*(g-1)/2;
ans+=1ll*query(r+1,n,1,d-1)*(x+g+v);
ans+=1ll*query(r+1,n,u+1,n)*(x+f+w);
ans+=1ll*query(r+1,n,d,u)*r;
printf("%I64d
",ans);
}
return 0;
//NOTICE LONG LONG!!!!!
}
D：显然每天要么不用优惠，要么就尽量用优惠。并且显然如果某天可以优惠到免费，使用优惠不会更劣。所以直接f[i][j]表示前i天剩余优惠为j时的最小代价，瞎转移即可，由上面的性质j不会超过21。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 300010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a[N],f[N][32];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();
for (int i=1;i<=n;i++) a[i]=read()/100;
memset(f,42,sizeof(f));f[0][0]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=30;j++)
if (j>=a[i]/10) f[i][j]=f[i-1][j-a[i]/10]+a[i];
for (int j=0;j<=30-a[i];j++)
f[i][j]=min(f[i][j],f[i-1][j+a[i]]);
for (int j=0;j<=a[i];j++) f[i][0]=min(f[i][0],f[i-1][j]+a[i]-j);
}
int ans=1000000000;
for (int i=0;i<=30;i++) ans=min(ans,f[n][i]);
cout<<100ll*ans;
return 0;
//NOTICE LONG LONG!!!!!
}