洛谷&&力扣儿
火星人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])本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！