Test 1023 T1&T2

2024-03-22 22:24:52

T1 popust (贪心

TimeLimit: 1000MS
Memory Limit: 32768KB

米尔科饿了如熊，偶然发现当地一家餐馆。餐厅提供$n$种餐，有一个有趣的定价政策：每种餐有两个指定的价格，$A_i$和$B_i$。米尔科支付第一种餐只能用价格$A$，后面的则只能支付$B$价格。他知道一种餐只能订一次，但不知道自己要订几种，于是他想知道从$1$种到$N$种的最少的费用（其实他不在意到底吃哪一种）。请你帮他想一下。

输入：

输入的第一行包含正整数$N(2≤N≤500000)$，餐厅提供的餐的种类数。
以下$N$行包含两个正整数，$A_i$和$B_i$$(1 ≤ Ai, Bi ≤ 1 000 000 000)$，表示第$i$种餐的两个价格。

输出：
$N$行，第$i$行表示恰好订$i$种餐的最低价格

input

output

9
13
18

input

2
100 1
1 100

output

1
2

input

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

output

意思就是选$x$种物品时，其中一个支付$A_i$，其余都支付$B_i$;

因为$A_i$只有一个，我们单独考虑；

如果只取$B$,我们一定是从小到大的取；

先排序；

我们首先从小到大取了$x$个$B$,现在要将其中一个改成$A$;

有两种改法；

在选的前$x$个$B$中，将其中一个改为对应的$A$，这一个物品的$A_i-B_i$,应该是前$x$个中最小的;
在没选的当中选一个最小的$A$,将最大的$B$改了；

第二种，我们可以预处理出$mina[]$代表第$i+1\sim n$中最小的$A$;

第一种可以用一个变量在求解时继承转移；

时间复杂度是$O(nlogn)$;

$Code$

#include<bits/stdc++.h> 
#define ll long long 
using namespace std;
const int N=500005;
int n,pos;
struct food
{
    int x,y;
    bool operator<(food w)const
    {
        return y<w.y;
    }
}a[N];
ll minx[N],minc;
ll ans;
inline int read()
{
    int x=0,f=1;char st=getchar();
    while(st<'0'||st>'9'){if(st=='-') f=-1;st=getchar();}
    while(st>='0'&&st<='9') x=x*10+st-'0',st=getchar();
    return x*f;
}

int main()
{
    freopen("popust.in","r",stdin);
    freopen("popust.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].x=read(),a[i].y=read();
    }
    sort(a+1,a+1+n);
    minx[n]=9999999999999;
    for(int i=n-1;i>=1;i--)
        minx[i]=min(minx[i+1],(ll)a[i+1].x);
    minc=9999999999999;
    for(int i=1;i<=n;i++)
    {
        minc=min(minc,(ll)a[i].x-a[i].y);
        ans+=a[i].y;
        printf("%lld\n",min(ans-a[i].y+minx[i],ans+minc));
    }
    
    
    fclose(stdin);
    fclose(stdout);
    return 0;   
}

T2 informacije （二分图

TimeLimit: 1000MS
Memory Limit: 32768KB

有一个序列$A$，包涵$1$到$N$共$N$个元素（每个元素出现且只出现一次），给出$M$个关于$A$的描述。描述格式如下：
$1 x y v $ 表示位置在$[x,y]$ 之间最大的值等于$v$
$2\ x\ y\ v$表示位置在$[x,y]$ 之间最小的值等于$v$
请输出满足上面这$M$个描述的序列。可以有不同的方案，输出任意一种。

无解输出$-1$;

$N (1 ≤ N ≤ 200)$$M (0 ≤ M ≤ 40 000)$

就是求合法排列；

就是求一个位置可以放什么数；

一边是位置，一边是数，一个位置可以选这个数就连一条边；

这是一个二分图；

位置与数相连代表这位置选这个数；

这就是二分图的最大匹配；

如果不是完备匹配，就构造不出排列；

就输出$-1$;

预处理出每个位置可以放的数，每个数可以放的位置，如果两情相悦，就连一条边；

时间复杂度是$O(n^3)$

$Code$

#include<bits/stdc++.h> 
#define ll long long 
using namespace std;
const int N=205;
int n,m,opt,l,r,v,ans;
bool pd[N][N];
int l1[N],l2[N];//上界，与下界
struct skr
{
    int to,nxt;
}a[N*N*2];
int head[N<<1],cnt;
int match[N<<1],vis[N<<1];
inline void add(int x,int y)
{
    a[++cnt].to=y;a[cnt].nxt=head[x];head[x]=cnt;
}
inline int read()
{
    int x=0,f=1;char st=getchar();
    while(st<'0'||st>'9'){if(st=='-') f=-1;st=getchar();}
    while(st>='0'&&st<='9') x=x*10+st-'0',st=getchar();
    return x*f;
}

inline bool dfs(int x)
{
    for(int i=head[x];i;i=a[i].nxt)
    {
        int y=a[i].to;
        if(!vis[y])
        {
            vis[y]=1;
            if(!match[y]||dfs(match[y]))
            {
                match[y]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    freopen("informacije.in","r",stdin);
    freopen("informacije.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)
        l1[i]=n,l2[i]=1;
    while(m--)
    {
        opt=read();l=read();r=read();v=read();
        for(int i=1;i<l;i++)
            pd[v][i]=1;
        for(int i=r+1;i<=n;i++)
            pd[v][i]=1;
        if(opt==1)
        {
            for(int i=l;i<=r;i++)
                l1[i]=min(l1[i],v);
        }
        else
        {
            for(int i=l;i<=r;i++)
                l2[i]=max(l2[i],v);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=l2[i];j<=l1[i];j++)
            if(!pd[j][i]) 
            {
                add(j,i+n);
                add(i+n,j);
            }
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof vis);
        if(dfs(i)) ans++;
    }
    if(ans<n)
    {
        printf("-1");
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",match[i+n]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

码农公寓

T1 popust (贪心

T2 informacije （二分图

相关文章