洛谷&&力扣儿

火星人https://www.luogu.com.cn/problem/P1088

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为?1,2,3,?1,2,3,?。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为?1,2,3,41,2,3,4?和?55，当它们按正常顺序排列时，形成了?55?位数?1234512345，当你交换无名指和小指的位置时，会形成?55?位数?1235412354，当你把五个手指的顺序完全颠倒时，会形成?5432154321，在所有能够形成的?120120?个?55?位数中，1234512345?最小，它表示?11；1235412354?第二小，它表示?22；5432154321?最大，它表示?120120。下表展示了只有?33?根手指时能够形成的?66?个?33?位数和它们代表的数字：

三进制数	代表的数字
123123	11
132132	22
213213	33
231231	44
312312	55
321321	66

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。
第一行一个正整数?�N，表示火星人手指的数目（1≤�≤100001≤N≤10000）。
第二行是一个正整数?�M，表示要加上去的小整数（1≤�≤1001≤M≤100）。
下一行是?11?到?�N?这?�N?个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式

�N?个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

输入输出样例

输入 #1复制

5
3
1 2 3 4 5

输出 #1复制

1 2 4 5 3

说明/提示

对于?30%30%?的数据，�≤15N≤15。

对于?60%60%?的数据，�≤50N≤50。

对于?100%100%?的数据，�≤10000N≤10000。

思路：使用内置函数next_permutation，可以得到当前排列的下一个比他大的排列

#include<bits/stdc++.h>
using namespace std;
#define itn int
int main()
{
	int n,k;
	cin>>n>>k;
	int a[100005];
	for (int i=0;i<n;++i)
	{
		cin>>a[i];
	}
	for (int i=0;i<k;++i)
	{
		next_permutation(a,a+n);
	}
	for (int i=0;i<n;++i)
	{
		cout<<a[i]<<" ";
	} 
}

刷题https://www.luogu.com.cn/problem/P1167

题目描述

NOIP 临近了，小 A 却发现他已经不会写题了。好在现在离竞赛还有一段时间，小 A 决定从现在开始夜以继日地刷题。也就是说小 A 废寝忘食，一天二十四小时地刷题。

今天的日期（时间）是 yyyy 年 mm 月 dd 日 hh 时 MM 分，考试的时间是 yyyy2 年 mm2 月 dd2 日 hh2 时 MM2 分。这之间的所有时间小 A 都用来刷题了，那么考试之前他最多能刷多少题呢？注意哦，考虑闰年。

时间紧张小 A 只管数量不管质量。当然有的题目容易一些，有的题目难一些。根据小 A 的经验，他能一眼看出写出某一个题目需要的时间，以分钟记。

现在给出洛谷 Online Judge 的题目列表，请你挑出最多的题目使小A能在竞赛前写出来。

我们假设从远古到未来，历法的表示与现在一样。

输入格式

第一行一个整数?�N，表示洛谷 Online Judge 的题目数，�≤5000N≤5000。

接下来�N行，每行一个整数表示刷该题需要用的时间，以分钟记（≤10000≤10000）。（这个题本身是什么并不重要，不是么？小A已经写过题目数为?00?个）。

接下来两行依次是当前时间和竞赛时间。时间给出的格式是：yyyy-mm-dd-hh:MM，例如：2007-06-23-02:00，采用?2424?小时制，每天从 00:00 到 23:59，年份从?00000000?到?99999999。

输出格式

一行，一个整数，NOIP 前最多刷的题目数。

输入输出样例

输入 #1复制

2
1
1
2007-06-23-11:59
2007-06-23-12:00

输出 #1复制

1

思路：这道题就暴力模拟一边就好了，运用时间差，来计算一共可以刷多少题

#include<bits/stdc++.h>
using namespace std;
#define itn int
bool leapyear(int year)
{
	if (year%100!=0 && year%4==0 || year%400==0) return true;
	else return false;
}
int m1[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int m2[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main()
{
	int n;
	int a[5005];
	cin>>n;
	for (int i=0;i<n;++i)cin>>a[i];
	sort(a,a+n);
	int cnt=0;
	int start[10],endd[10];
	scanf("%d-%d-%d-%d:%d",&start[1],&start[2],&start[3],&start[4],&start[5]);
    scanf("%d-%d-%d-%d:%d",&endd[1],&endd[2],&endd[3],&endd[4],&endd[5]);
	long long  total_time=0;
	for (int i=start[1];i<endd[1];++i)
	{
		if (leapyear(i))
		{
			total_time+=366;
		}
		else 
		{
			total_time+=365;
		}
	}
	if (leapyear(start[1]))
	{
		for (int i=1;i<start[2];++i)
		{
			total_time-=m2[i];
		}
	}
	else 
	{
		for (int i=1;i<start[2];++i)
		{
			total_time-=m1[i];
		}
	}
	if (leapyear(endd[1]))
	{
		for (int i=1;i<endd[2];++i)
		{
			total_time+=m2[i];
		}
	}
	else 
	{
		for (int i=1;i<endd[2];++i)
		{
			total_time+=m1[i];
		}
	}
	for (int i=1;i<start[3];++i)
	{
		total_time--;
	}
	for (int i=1;i<endd[3];++i)
	{
		total_time++;
	}
	total_time=total_time*24*60;
	total_time-=60*start[4]+start[5];
    total_time+=60*endd[4]+endd[5];
    for (int i=0;i<n;++i)
    {
    	if (total_time>=a[i])
    	{
    		total_time-=a[i];
    		cnt++;
		}
		else 
		{
			break;
		}
	}
	cout<<cnt;
	
}

借教室https://www.luogu.com.cn/problem/P1083

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来?�n?天的借教室信息，其中第?�i?天学校有?��ri??个教室可供租借。共有?�m?份订单，每份订单用三个正整数描述，分别为?��,��,��dj?,sj?,tj?，表示某租借者需要从第?��sj??天到第?��tj??天租借教室（包括第?��sj??天和第?��tj??天），每天需要租借?��dj??个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供?��dj??个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第?��sj??天到第?��tj??天中有至少一天剩余的教室数量不足?��dj??个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数?�,�n,m，表示天数和订单的数量。

第二行包含?�n?个正整数，其中第?�i?个数为?��ri?，表示第?�i?天可用于租借的教室数量。

接下来有?�m?行，每行包含三个正整数?��,��,��dj?,sj?,tj?，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从?11?开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数?00。否则（订单无法完全满足）

输出两行，第一行输出一个负整数??1?1，第二行输出需要修改订单的申请人编号。

输入输出样例

输入 #1复制

4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

输出 #1复制

-1 
2

说明/提示

【输入输出样例说明】

第?11份订单满足后，44天剩余的教室数分别为?0,3,2,30,3,2,3。第?22?份订单要求第?22天到第?44?天每天提供33个教室，而第?33?天剩余的教室数为22，因此无法满足。分配停止，通知第22?个申请人修改订单。

【数据范围】

对于10%的数据，有1≤�,�≤101≤n,m≤10；

对于30%的数据，有1≤�,�≤10001≤n,m≤1000；

对于 70%的数据，有1≤�,�≤1051≤n,m≤105；

对于 100%的数据，有1≤�,�≤106,0≤��,��≤109,1≤��≤��≤�1≤n,m≤106,0≤ri?,dj?≤109,1≤sj?≤tj?≤n。

思路：主要用前缀和差分来解

定义一个新的函数，模拟前x次订单是否满足，然后通过二分的方法，慢慢找到订单

#include<bits/stdc++.h>
using namespace std;
#define itn int
#include <stdio.h>
#include <string.h>
long long  diff[11000011],need[1000011],rest[1000011],d[1000011],s[1000011],t[1000011];
int n,m;
bool blbl(int x)
{
	memset(diff,0,sizeof(diff));
	for (int i=1;i<=x;++i)
	{
		diff[s[i]]+=d[i];
		diff[t[i]+1]-=d[i];
	}
	for (int i=1;i<=n;++i)
	{
		need[i]=need[i-1]+diff[i];
		if (need[i]>rest[i]) return false;
	}
	return true;
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>> rest[i];
	for (int i=1;i<=m;++i) cin>>d[i]>>s[i]>>t[i];
	int l=1,r=m;
	if (blbl(m)) {
		cout<<"0";
		return 0;
	}
	while (l<r)
	{
		int mid=l+(r-l)/2;
		if (blbl(mid))l=mid+1;
		else r=mid;
	}
	cout<<"-1"<<endl<<l;
} 

力扣：

题1https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/

思路：就是找最小值，没必要多看

int findMin(int* nums, int numsSize) {
    int mins=nums[0];
    for (int i=1;i<numsSize;++i)
    {
        if (mins>nums[i])mins=nums[i];
    }
    return mins;
}

class Solution:
    def findMin(self, nums: List[int]) -> int:
        mins=min(nums)
        return mins

题2https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/description/

思路：也还是找最小

int stockManagement(int* stock, int stockSize) {
    int mins=stock[0];
    for (int i=1;i<stockSize;++i)
    {
        if (mins>stock[i])mins=stock[i];
    }
    return mins;
}

class Solution:
    def stockManagement(self, stock: List[int]) -> int:
        return min(stock)

题3：https://leetcode.cn/problems/third-maximum-number/description/

思路：这题，主要要降序排一次就ok，至于为啥升序不行，还没弄清

int  cmp(const void *a,const void *b)
{
    return *(int *)a<*(int *)b;
}
int thirdMax(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(nums[0] ),cmp);
    int cnt=1;
    for (int i=1;i<numsSize;++i)
    {
        if (nums[i]!=nums[i-1])
        {
            cnt++;
            if (cnt==3)return nums[i];
        }
    }
    return nums[0];
}

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        a=[]
        for i in nums:
            if not i in a:
                a.append(i)
        if len(a)<3:
            return a[0]
        else :
            return a[2]

题4：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/

思路：好题好题，当时写的时候脑子短路，百思不得其解，看来题解顿悟，原来只要比较前三的正数（就是排完序后最大的三个数）的乘积，和最小和次小两个数和最大数的乘积的ok

int  cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
// 
int maximumProduct(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof (nums[0]),cmp);
    return fmax(nums[0]*nums[1]*nums[numsSize-1],nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3]);
}

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        l=len(nums)
        return max(nums[0]*nums[1]*nums[l-1],nums[l-1]*nums[l-2]*nums[l-3])