【寒假训练/Java】贪心专题
文章目录
题目链接
贪心专题-牛客链接
比赛密码：202302010213
题目列表
快输
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args)
{
out.flush();
}
static class FastReader{
BufferedReader br;
StringTokenizer st;
String tmp;
public FastReader() {
br=new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while(st==null||!st.hasMoreElements()) {
try {
st=new StringTokenizer(br.readLine());
}catch(IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong(){return Long.parseLong(next());}
String nextLine() {
String str="";
try {
str=br.readLine();
}catch(IOException e) {
e.printStackTrace();
}
return str;
}
boolean hasNext(){
if(st!=null&&st.hasMoreTokens())return true;
try {
tmp=br.readLine();
st=new StringTokenizer(tmp);
}catch(IOException e) {
return false;
}
return true;
}
}
static PrintWriter out=new PrintWriter(
new BufferedWriter(new OutputStreamWriter(System.out)));
static FastReader sc=new FastReader();
}
A - 最小生成树
最小生成树:
一个有N个点的图，其最小生成树就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。
题目中说明这张无向图是一张完全图，则可以先求得权值最小的顶点；根据前面的条件，通过该点连接其他所有点,这样得到的边权之和一定最小。
public static void main(String[] args)
{
long sum=0,min=(long)1e9+7,x,n;
n=sc.nextInt();//输入n个点，最小生成树一共有n-1条边
for(int i=0;i<n;i++)
{
x=sc.nextInt();
sum+=x;
min=Math.min(x,min);
}
out.println(sum+(n-2)*min);
out.flush();
}
B - [USACO 2006 Oct S]Fence Repair
说明部分可以理解为，为使代价最小，每次应选择长度最短的两根木头，并将二者长度之和作为整体存入。
即构造哈夫曼树的过程，使用优先队列减少排序时间。
public static void main(String[] args)
{
int n=sc.nextInt(),t;
PriorityQueue<Integer> pq=new PriorityQueue<>(n);
for(int i=0;i<n;i++) pq.add(sc.nextInt());
long ans=0;
while(pq.size()>=2)
{
t=pq.poll()+pq.poll();
ans+=t;
pq.add(t);
}
out.println(ans);
out.flush();
}
C - money
题意是一共n个商店，每个商店可以有两个选择：花费ai价值买入 或者 卖出以获得ai价值；但当前拥有的物品数不能超过1，即不能连续买入；求最终获得的最大价值及最小交易次数。
解法为每次都在一个上升子串的低点买入，高点卖出（贪心思想），这样获得的价值最大，同时交易次数最少。
本质即是求不重叠上升子串的数目，最大价值为高点 - 低点之和，最小交易次数为子串数目*2（买入和卖出共交易两次）。
public static void main(String[] args)
{
int T=sc.nextInt(),n;
long[] a;//商店价值数组
while(T-->0)//测试样例数目
{
n=sc.nextInt();//商店数目
long pre=0,s=0,t=0;//上升子串的低点，总价值，交易次数
a=new long[n];
boolean f=false;//判断当前是否为上升子串
a[0]=sc.nextLong();
for(int i=1;i<n;i++)
{
a[i]=sc.nextLong();
if(!f&&a[i]>a[i-1])
{//进入上升子串，标记第一个值为低点
f=true;
pre=a[i-1];
}
if(f&&a[i]<a[i-1])
{
s+=a[i-1]-pre;
f=false;
t++;
}
}
if(f)
{//最后一个上升子串持续到结尾的情况
s+=a[n-1]-pre;
t++;
}
out.println(s+" "+t*2);
}
out.flush();
}
D - 大吉大利，今晚吃鸡——枪械篇
枚举+模拟
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
int n=sc.nextInt(),m=sc.nextInt(),p,k;//枪支数量和配件数量
ArrayList<Integer>[] ls=new ArrayList[n];//存入枪支威力p，配件数量k，及k个配件种类
for(int i=0;i<n;i++)
{
ls[i]=new ArrayList<>();
p=sc.nextInt();
k=sc.nextInt();
ls[i].add(p);
ls[i].add(k);
for(int j=0;j<k;j++) ls[i].add(sc.nextInt());
}
double[] a=new double[1001];//配件可以为枪支提供的威力加成
while(m-->0)
{
int q=sc.nextInt();//配件种类
double b=sc.nextDouble();//威力加成
a[q]=Math.max(a[q],b);
}
double ans=0,sum;
for(int i=0;i<n;i++)
{
sum=1;
p=ls[i].get(0);
k=ls[i].get(1);
for(int j=2;j<k+2;j++)
{
sum+=a[ls[i].get(j)];
}
ans=Math.max(ans,p*sum);
}
out.printf("%.4f\n",ans);
}
out.flush();
}
static PrintWriter out = new PrintWriter(
new BufferedWriter(new OutputStreamWriter(System.out)));
}
E - 世界上最可爱的珂朵莉
public static void main(String[] args)
{
int n=sc.nextInt();
long x=sc.nextInt(),y=sc.nextInt(),ans=0;
long[] a=new long[n],b=new long[n];
for(int i=0;i<n;i++)
a[i]=sc.nextLong();
for(int i=0;i<n;i++)
b[i]=sc.nextLong();
Arrays.sort(a);
Arrays.sort(b);
for(int i=0;i<n;i++)
{
if(x==0||a[i]>=y)break;
a[i]=y;
x--;
}
Arrays.sort(a);
for(int i=0;i<n;i++)
{
ans=Math.max(ans,b[i]-a[i]);
}
out.println(ans);
out.flush();
}
F - 牛牛的排序
public static void main(String[] args)
{
int n=sc.nextInt(),max=0,min=1001;
int[] a=new int[n],b=new int[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
b[i]=a[i];
max=Math.max(a[i],max);
min=Math.min(a[i],min);
}
Arrays.sort(b);
//a数组本身就是升序排列，无序再次排序
if(Arrays.equals(a,b))
out.println(0);
else
{
if(a[0]==min||a[n-1]==max)out.println(1);
else if(a[0]==max&&a[n-1]==min)out.println(3);
else out.println(2);
}
out.flush();
}
G - 牛牛的朋友
在升序排列的数组中，枚举每一个点，假设当前点左侧全部右移，右侧全部左移，求得其中移动后左右端点的最小距离。
public static void main(String[] args)
{
int n=sc.nextInt();
int[] p=new int[n];
for(int i=0;i<n;i++)p[i]=sc.nextInt();
Arrays.sort(p);
int x=sc.nextInt(),ans=p[n-1]-p[0];
for(int i=0;i<n-1;i++)
{
//左边界二选一：左端点右移后的位置 or 当前点右侧的端点左移后的位置
int l=Math.min(p[0]+x,p[i+1]-x);
int r=Math.max(p[n-1]-x,p[i]+x);
ans=Math.min(ans,r-l);
}
out.println(ans);
out.flush();
}
H - 货币系统（完全背包）
- 为满足 (m,b) 与原来的货币系统 (n,a) 等价，则面额数组b是面额数组a的子数组；
- 为使m 尽可能的小，则应使面额数组b中的任意元素不能被其他元素所表示。
又即通过完全背包判断a数组中的每一个元素是否可以通过若干其他元素相加得到，如果不能则表示该元素不可替代，需要被放入b数组。
public static void main(String[] args)
{
int T=sc.nextInt();
int n,ans;
int[] a,dp;
while(T-->0)
{
ans=0;
n=sc.nextInt();
a=new int[n];
for(int i=0;i<n;i++)a[i]=sc.nextInt();
Arrays.sort(a);
int tp=a[n-1];//a[n-1]即为max
dp=new int[tp+1];//0~max
dp[0]=1;
//a[0]~a[i-1]可以选择无限个 - 完全背包
for(int i=0;i<n;i++)
{
//判断当前的a[i]是否可以由之前的a[0]~a[i-1]表示出来
//dp[i]表示面额为i的时候的方案数目
if(dp[a[i]]==0) ans++;
for(int j=a[i];j<tp+1;j++)dp[j]+=dp[j-a[i]];
}
out.println(ans);
}
out.flush();
}
I - [CQOI2014]通配符匹配（DP&字符串哈希）
DP+字符串哈希：洛谷P3167 【[CQOI2014]通配符匹配】
static long key=19260817;
static long[] pre=new long[100010],mul=new long[100010],h=new long[20];
static int n,cnt;
static int[] sp=new int[20],stl=new int[20],dp[]=new int[15][100010];
static char[] a=new char[100010],b[]=new char[15][100010];
public static void main(String[] args)
{
a=sc.next().toCharArray();
int i,j,l,len=a.length;
long t1;
mul[0]=1;
for(i=1;i<=100000;i++) mul[i]=mul[i-1]*key;
if(a[0]=='*'||a[0]=='?') h[++cnt]=gethash(b[cnt],stl[cnt]=0);
for(i=0;i<len;)
{
if(a[i]=='*'||a[i]=='?')
{
sp[cnt]=(sp[cnt]!=0||(a[i]=='*'))?1:0;
i++;
}
j=0;cnt++;
while(i<len&&a[i]!='*'&&a[i]!='?')
{
b[cnt][j]=a[i];
i++;
j++;
}
h[cnt]=gethash(b[cnt],stl[cnt]=j);
}
len++;
if(a[len-2]=='*'||a[len-2]=='?')
{
cnt++;
h[cnt]=0;
sp[cnt]=stl[cnt]=0;
}
else sp[cnt]=0;
n=sc.nextInt();
for(l=1;l<=n;l++)
{
a=(sc.next()+" ").toCharArray();
len=a.length-1;
a[len]='$';
len++;
for(int[] ints:dp)Arrays.fill(ints,-1);
dp[0][0]=2;pre[0]=0;
for(i=0;i<len;i++) pre[i+1]=pre[i]*key+(long)a[i];
for(j=0;j<=len;j++)
{
for(i=0;i<=cnt;i++)
{//只有这里有差别
if(dp[i][j]==-1) continue;
if(dp[i][j]==1) dp[i][j+1]=1;
if(dp[i][j]==0)
{
dp[i][j]=2;
if(dp[i][j+1]==-1) dp[i][j+1]=2;
if(dp[i][j+1]==0) dp[i][j+1]=3;//判断赋2还是3
continue;
}
if(dp[i][j]==3)
{
dp[i][j]=2;
if(dp[i][j+1]==-1) dp[i][j+1]=2;
if(dp[i][j+1]==0) dp[i][j+1]=3;//判断赋2还是3
}
t1=pre[j+stl[i+1]]-pre[j]*mul[stl[i+1]];
if(t1==h[i+1])
{
dp[i+1][j+stl[i+1]]=Math.max(dp[i+1][j+stl[i+1]],sp[i+1]);
}
}
}
if(dp[cnt][len]!=-1) out.println("YES");
else out.println("NO");
}
out.flush();
}
static long gethash(char[] s,int len)
{
long re=0;int i;
for(i=0;i<len;i++)
{
re*=key;
re+=s[i];
}
return re;
}
贪心解法参考：TLE
static char[] p,s;//模式串，文本串
public static void main(String[] args)
{
p=sc.next().toCharArray();
int T=sc.nextInt();
while(T-->0)
{
s=sc.next().toCharArray();
if(f()) out.println("YES");
else out.println("NO");
}
out.flush();
}
static boolean f()
{
int i=0, j=0, iStar=-1, jStar=-1, m=s.length, n=p.length;
while (i<m) {
if (j<n&&s[i]==p[j]||p[j]=='?')//可以匹配，双指针向后顺移
{
++i;
++j;
} else if (j<n&&p[j]=='*')//记录如果之后序列匹配不成功时， i和j需要回溯到的位置
{
iStar=i;//记录星号
jStar=j++;//记录星号 并且j移到下一位 准备下个循环s[i]和p[j]的匹配
} else if (iStar>=0)//发现字符不匹配且没有星号出现 但是istar>0 说明可能是*匹配的字符数量不对 这时回溯
{
i=++iStar;//i回溯到istar+1 因为上次从s串istar开始对*的尝试匹配已经被证明是不成功的（不然不会落入此分支） 所以需要从istar+1再开始试 同时inc istar 更新回溯位置
j=jStar+1;//j回溯到jstar+1 重新使用p串*后的部分开始对s串istar（这个istar在上一行已经inc过了）位置及之后字符的匹配
} else return false;
}
while (j<n&&p[j]=='*') ++j;//去除多余星号
return j==n;
}
J - 牛牛学括号
题目给出的括号序列是合法的，那么左右括号一定匹配，且第一个括号为左括号。
维护一个栈，只存入左括号，遇到右括号则进行删除操作，可以删除的位置种类为栈的长度，因此要使当前结果✖栈长度。
public static void main(String[] args)
{
int mod=(int)1e9+7;
char[] s=sc.next().toCharArray();
int l=s.length;
long sum=1;
Stack<Character> st=new Stack<>();
for(int i=0;i<l;i++)
{
if(s[i]=='(') st.push(s[i]);
else
{
sum=(sum*st.size())%mod;
st.pop();
}
}
out.println(sum);
out.flush();
}
K - [HAOI2008] 糖果传递（数学&贪心）
数学+贪心：解法参考
public static void main(String[] args)
{
int n=sc.nextInt();
long sum=0;
long[] a=new long[n+1],b=new long[n+1],Sum=new long[n+1];
for(int i=1; i<=n; i++)
{
a[i]=sc.nextLong();
Sum[i]=Sum[i-1]+a[i];
sum+=a[i];
}
long ave=sum/n;
for(int i=1;i<n;i++)
b[i]=Sum[n-1]-Sum[i-1]-(n-i)*ave;
b[n]=0;
Arrays.sort(b,1,n+1);
long x=b[(n+1)/2];
sum=0;
for(int i=1;i<=n;i++)
sum+=Math.abs(x-b[i]);
out.println(sum);
out.flush();
}
L - 青蛙（二分）
public static void main(String[] args)
{
int T=sc.nextInt();
while(T-->0)
{
int n=sc.nextInt(),m=sc.nextInt(),d=sc.nextInt();
int[] a=new int[m+2];
for(int i=0;i<m+2;i++)
a[i]=sc.nextInt();
int l=1,r=m;//最多m只青蛙
while(l<=r)
{
int mid=(l+r)>>1,f=1;
//check部分，判断当前只数的青蛙能否跳到终点
for(int i=0;i+mid<m+2;i++)
if(a[i+mid]-a[i]>d)
{
f=0;
break;
}
if(f!=0) l=mid+1;
else r=mid-1;
}
out.println(r);
}
out.flush();
}
标解
public static void main(String[] args)
{
int T=sc.nextInt();
while(T-->0)
{
int n=sc.nextInt(),m=sc.nextInt(),d=sc.nextInt();
m+=2;
int[] a=new int[m+1];
for(int i=1;i<=m;i++)
a[i]=sc.nextInt();
int r=1;
int ans=2147483647;
for(int i=1;i<=m;i++)
{
while(r<=m&&a[r]-a[i]<=d) r++;//当前位置可以跳的选择数量
ans=Math.min(ans,r-i-1);//取每个位置可选择跳的最小值即为可过的青蛙
if(r==m+1) break;
}
out.println(ans);
}
out.flush();
}
M - 吃货（二分）
结构体 - 将食物按照价格升序排列，同等价格下，按照美味度降序排列。
美味度更新 - 当前价格之下有更高的美味度，则需要更新
二分 - 找到小于等于携带钱数的食物的最高美味度，因为之前进行了更新，只需要找到对应价格的食物即可。
import java.io.*;
import java.util.*;
class Node implements Comparable<Node>
{
int d,c;//价格, 美味度
Node(int d,int c)
{
this.d=d;
this.c=c;
}
@Override
public int compareTo(Node o)
{
if(d==o.d)
return o.c-c;//同等价格，美味度降序排列
return d-o.d;//价格按升序排列
}
}
public class Main
{
public static void main(String[] args)
{
int T=sc.nextInt();
while(T-->0)
{
int n=sc.nextInt(),m=sc.nextInt();
Node[] a=new Node[n];
for(int i=0;i<n;i++)
a[i]=new Node(sc.nextInt(),sc.nextInt());
Arrays.sort(a);
int t=0;//获得当前最高美味度
for(int i=0;i<n;i++) //价格高的可以获得前面最高的美味度
{
if(a[i].c<t)
a[i].c=t;
else
t=a[i].c;
}
while(m-->0)//m次询问
{
int ans=0;
t=sc.nextInt();//钱数
int l=0,r=n-1;//枚举下标，找价格小于等于t的物品的最大美味度
while(l<=r)
{
int mid=(l+r)>>1;
if(t<a[mid].d) r=mid-1;
else
{
if(ans<a[mid].c)
ans=a[mid].c;
l=mid+1;
}
}
out.println(ans);
}
}
out.flush();
}
//快输 - 经测试不使用快输会TLE
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
boolean hasNext() {
if (st != null && st.hasMoreTokens())
return true;
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
return false;
}
return true;
}
}
static PrintWriter out = new PrintWriter(
new BufferedWriter(new OutputStreamWriter(System.out)));
static FastReader sc=new FastReader();
}